educative.io

Wouldn't the time complexity be a n^4 in the worst case?

Courses
,
#1

If we imagine a worst case as the grid consisting of the letters that each start a word of length that spans the entire grid, which is n * n, then (as given by the solution) we loop over each element of the grid, which is n * n times. So for each character in the grid that we start from, we have to explore n * n - 1 other characters.
For example grid:
a, b, c
d, e, f
g, h i

and dictionary:
"abcdefghi", "bacdefghi", cbadeghgi", .... "ihgfedcba"

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5679846214598656
Lesson: https://www.educative.io/collection/page/5642554087309312/5679846214598656/170002

#2

@Peter_Litvak

In the worst case time complexity will be n^n, because as the dictionary grows dynamically the range will expand accordingly, since backtracking is used in this question thus recursive functions will be called inside loops, and as said earlier that as the dictionary grows dynamically the range will expand accordingly so for the worst case we will have n^n. n^4 would lie for a specific case which is mentioned by you but that is not the worst case.