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)?