Basic Time Complexity

[ddalgibbang]

Hello
Please excuse my lack of knowledge to python, but I just cannot understand how time complexity works. I've read many threads on this forum regarding time complexity but I am still quite confused.

Our prof has given us this example:

def foo(n):
! while (n > 0):
! ! print n
! ! n = n / 2

and this answer:

complexity = 3n + 1
! simplifying:
! ! removing constants: complexity = O(n) eg- linear with "n"

I understand that a while loop will produce N and if you simplify you will get O(N).
But how do you get 3n + 1 before simplifying to the big O?

[slate]

You enter the function that is one.

Then you make n times, the followings:
1. You check if n>0
2. You print n
3. You divide n by 2 and store it in n

Practically the first line is executed once, the other three executed n times.

[Gribouillis]

You enter the function that is one.

Then you make n times, the followings:
1. You check if n>0
2. You print n
3. You divide n by 2 and store it in n

Practically the first line is executed once, the other three executed n times.

Actually, the loop's body is executed 1 + log(n)/log(2) times (for n > 0).

[slate]

Yes you are right, my mistake. Then I do not understand it eighter.

[ddalgibbang]

Actually, the loop's body is executed 1 + log(n)/log(2) times (for n > 0).

Do you think you can explain why it is 1 + log(n)/log(2) times?
Thanks so much

[TrustyTony]

Reducing by one bit counter by /2 -> log2 of counter times.

[Gribouillis]

Do you think you can explain why it is 1 + log(n)/log(2) times?
Thanks so much

I give 2 explanations. The first one is by experiment: let's print the binary representation of n while the loop is executed

# python 2.6

def foo(n):
    while (n > 0):
        print bin(n), n
        n = n / 2

if __name__ == "__main__":
    foo(23676786876)

"""my output -->
0b10110000011001111110001100010111100 23676786876
0b1011000001100111111000110001011110 11838393438
0b101100000110011111100011000101111 5919196719
0b10110000011001111110001100010111 2959598359
0b1011000001100111111000110001011 1479799179
0b101100000110011111100011000101 739899589
0b10110000011001111110001100010 369949794
0b1011000001100111111000110001 184974897
0b101100000110011111100011000 92487448
0b10110000011001111110001100 46243724
0b1011000001100111111000110 23121862
0b101100000110011111100011 11560931
0b10110000011001111110001 5780465
0b1011000001100111111000 2890232
0b101100000110011111100 1445116
0b10110000011001111110 722558
0b1011000001100111111 361279
0b101100000110011111 180639
0b10110000011001111 90319
0b1011000001100111 45159
0b101100000110011 22579
0b10110000011001 11289
0b1011000001100 5644
0b101100000110 2822
0b10110000011 1411
0b1011000001 705
0b101100000 352
0b10110000 176
0b1011000 88
0b101100 44
0b10110 22
0b1011 11
0b101 5
0b10 2
0b1 1
"""

at each step, one binary digit of n is removed, so the number of binary digits of n gives the number of times the loop's body is executed.

Now a mathematical proof. The binary representation of n > 0 starts with 1 in position k >= 0. It means that 2^k <= n < 2^{k+1}. So we have k log(2) <= log(n) < (k+1) log(2) and finally k <= log(n)/log(2) < k+1. This means that k is the integer part of log(n)/log(2)
The number of binary digits of n (including the leading 1) is 1+k = 1 + int(log(n)/log(2)). This is the number of times the loop is traversed.

In terms of complexity theory, you would say that this function has a complexity of O(log(n))