educative.io

Educative

Explain Runtime Please

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?

  1. The recursive helper is being called n times
  2. The helper func contains a for loop going from start to end
  3. Inside the for loop you’re checking if the substring formed by start + end is a palindrome
  4. 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