educative.io

Educative

How's brute force time complexity O(3^N)?

Longest Palindromic Substring brute-force:
“Due to the three recursive calls, the time complexity of the above algorithm is exponential O(3^n)O(3
​n
​​ ), where ‘n’ is the length of the input string. The space complexity is O(n)O(n) which is used to store the recursion stack.”

How is this 3^N? I think it should be N^2 or N^3. Please clarify in the explanation for time analysis for this problem

Did you understand why 0/1 Knapsack algorithm is O(2^n)? Following the same logic, this algorithm is O(3^n).

For 0/1 Knapsack, focus on this part:

The above algorithm’s time complexity is exponential O(2^n)​​ , where ‘n’ represents the total number of items. This can also be confirmed from the above recursion tree. As we can see that we will have a total of ‘31’ recursive calls – calculated through (2^n) + (2^n) - 1​, which is asymptotically equivalent to O(2^n).

For a string with size N, there is N(N+1)/2 substrings => N^2
To verify a substring is a palindrome, we need O(K) where K’s upper limit = N and lower limit = 1 => avg = N/2

Doesn’t that make it O(N^3) for the brute force method? How did we arrive at O(3^N)?

1 Like