What will be the time complexity of following recursive function?
f(int n) {
if(n <= 1) {
return;
}
f(n/2);
f(n/2);
}
Time Complexity
hey @riyajain2372_a386c6cc4ebaf1b9 Refer to the calculations below If something is not understandable in the image feel free to ask.
Your ans is T(n) = 2^logn
where log is of base 2
So in turn 2 to the power of log base 2 n will be equal to n, right?
Is the time complexity actually O(n)?
@riyajain2372_a386c6cc4ebaf1b9 Yes It can be further shortened to O(n). This can be verified by master theorem also.
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.