educative.io

Educative

My understanding of the Time Complexity Question

Assuming the grid is of NxN,

select every possible start position, and for each start position, try all the possible next position to build string, till all the adjacent positions are already used. the whole iteration is

Number of possible start positions: N^2
Maximum number of possible string length: N^2
Max possible steps after we choose the first letter: N^2-1
In every step max possible grid: 8

time complexity:
O (N^2 * 8^(N^2 -1) )
= O( 8^(N^2))

when using recursion to add next character, the most depth of recursion can be N^2, meaning, in one try we use all the letters in the grid.

Hey I agree with you, I think the O(N^N) they quote is wrong. One question, why do you convert O (N^2 * 8^(N^2 -1) ) = O( 8^(N^2)) ?

Didn’t know exponentials absorbed multiplications in Big O format. Is there a resource you’d recommend for this?