If it will take N+N/2+N/4…1 time then is this not equal to 2^(N-1)-1 and therefore O(2^N)? Also, if the first loop itself takes N time and how can this be upper bound by N?
Quiz on Time and Space Complexity Q1
@SMRITI
For a input integer n, the innermost statement is executed following times.
n + n/2 + n/4 + … 1 <= 2*n (using infinite gp formula -> A / (1-R) )
hence the time complexity will be O(N)
Thanks! Thats helpful.
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.