If we do the backtracking, what is the bigO runtime?


  • 0
    O

    assuming string is "abcdefghijklmn ... "

    essentially becomes

    T(N) = "a" + T(N-1) +
    "ab" + T(N-2) +
    "abc" + T(N-3) +
    ...
    ...

    there will be N constant terms, so

    T(N)

    = N + T(N-1) + T(N-2) + T(N-3) + ...

    = N + N + N ...

    = N^2

    is that N^2 runtime?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.