Time complexity of a specific function in python

Question

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.

Is the answer completely correct? What do you think it should be? — Mechanic Pig
– Mechanic Pig, Commented Sep 20, 2022 at 14:37
the answer is O(√n), its a question from a test but I don't understand the reason behind it — Liel Azulay
– Liel Azulay, Commented Sep 20, 2022 at 14:38
yes since √n is a tight upper bound, my question is why this is the answer I'm trying to understand how to get to the answer — Liel Azulay
– Liel Azulay, Commented Sep 20, 2022 at 14:42
In short: how many times can you double jump before cur exceeds n? — chepner
– chepner, Commented Sep 20, 2022 at 15:12

Mechanic Pig · Accepted Answer · 2022-09-20 15:50:35Z

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.}

Collectives™ on Stack Overflow

Time complexity of a specific function in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related