Big O Notation-Please explain O(log2n)

Question

I'm having trouble understanding why this piece of code is O(log 2^n) for its Big O Notation:

for (int i = n; i>=1; i=i/2){
    sum = i+j;
}

I thought it would be O(n).

Solution 1

This is O(log_2 n). Because it will run until n becomes 1.

After k th step suppose the whole things become 1.

So n/2^k = 1

k=log_2 n

The complexity is O(log_2 n)

Solution 2

Simple answer:

As @coderredoc explained this code snippet is O(log n). Base of logarithm is immaterial in asymptotic notations because it only make difference of constants.

In-depth answer: If this is asked in the academic context; then please read more about difference between big-O notation and big-Θ notation. http://web.mit.edu/16.070/www/lecture/big_o.pdf https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation

For your specific question, any code which is O(log n) can theroritically said to be O(2^n) or O(n) or O(log 2^n). Because, big-O notation describes the upped bound and not the tight bound.