Hi I'm trying to understand why the time complexity of the next function:
def f(n): result = 0 jump = 1 cur = 0 while cur < n: result += cur if jump*jump < n: jump *= 2 cur += jump return result is O(√n). I understand that the code under the if statement inside the function gets executed until jump >= √n, I also noticed that cur = 1 + 2 + 4 + 8 + 16 + ... but I still can't get the answer.
A little math is needed here.
Suppose that jump^2 is greater than or equal to n after m iterations, and then the jump will not be doubled again. Here we have:
jump = 2^m >= √n At this time, cur is:
cur = 1 + 2 + 4 + ... + 2^m = 2 ^ (m + 1) - 1 Then, our total number of iterations will not be greater than:
n - (2 ^ (m + 1) - 1) m + ceil( --------------------- ) 2^m Because we have 2^m >= √n and 2 ^ (m - 1) < √n, so
n - (2 ^ (m + 1) - 1) m + ceil( --------------------- ) 2^m n - 2√n + 1 < (log √n + 1) + (----------- + 1) 2 √n n + 1 = log √n + ----- 2 √n Here, it is clear that (n + 1) / √n is O(√n), and the logarithm is also O(√n), so the sum of the two is O(√n).
Because it is about time complexity, we can prove it more loosely. For example, before jump reaches √n, it is O(log_2 √n) complexity, and after that, it is O(√n) complexity. The sum of the two is obviously O(√n) complexity.
jumpbeforecurexceedsn?