What will be the time complexity of the editorial code , will it be O(n^3) as we are recursively calling for all (si, en) and a for loop is there for finding the point where the left and right subarray are equal.
Time Complexity of the editorial
@Vishal_234 It is not going to be n^3 complexity. It does look like n^3 but as you can see that the size of the array decreases exponentially the time complexity would be even less than n^2. As you must be knowing that the array reduce like:
n + n/2 + n/4 +… n/k.
Where k= 2^p.
And the complexity for this would be close to n*4. So you can see that it is going to be close to logarithmic complexity for this solution.
I would leave the proof for you as a homework.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.