CODEWITHSUNDEEP
pythontime-complexity
Liel Azulay
Liel Azulay

Reputation: 99

Time complexity of a specific function in python

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.

Upvotes: 5

Views: 123

Answers (1)

Mechanic Pig
Mechanic Pig

Reputation: 7736

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.

Upvotes: 3

Related Questions