This brute force approach is different than the ones explained in previous questions where it does not use a for loop to recurse. I do not understand why it is 2^n. Prior to this question I would count the number of recursion functions that span, here there is only one in the for loop. Can you please explain how you got the 2^n?
2 Likes
I agree. it should be n^n
1 Like
Isn’t the time complexity for the brute force solution n^4 in the worst case?
- The recursive helper is being called n times
- The helper func contains a for loop going from start to end
- Inside the for loop you’re checking if the substring formed by start + end is a palindrome
- Inside the if statement (which is inside the for loop), you’re making a recursive call
nnn*n. Or so it would seem to me!
Please answer this question @Design_Gurus, it’s seem a bit complicated to me when calculating time complexity. Thanks.
1 Like