Why is the time complexity O(log n)?

Question

int algorithm(int n) {
    int k = 0;
    while(n>1) {
       n=n/2;  // integer division
       k++;
    }
    return k;
}

Time complexity is O(log n)? Why?

Because this is the number of iterations and the time complexity of the loop body is O(1). — Henry, Jan 26 '18 at 07:53
This follows almost directly from the definition of log, you should probably start there. — Bernhard Barker, Jan 26 '18 at 10:36

score 4 · Answer 1 · 2018-01-26T08:11:42.307

If you write n as a binary number, say 11011011, the successive values it takes before the loop exits are

Therefore, the number of iterations (final value of k) equals the initial number of bits of n. From

2^(k-1) ≤ n < 2^k

which is the condition to have k bits, you draw

k-1 ≤ log2(n) < k.

score 1 · Answer 2 · answered Jan 26 '18 at 08:05

1

The reason is that the operations in the loop, division and addition, are O(1). Now, consider the number of iterations for n = 2^m, for some m, and compare this number with log_2(n). Generalising to n, which are not powers of 2 is easy. Denoting by i(n) the number of iterations of the loop for input n, and taking for 2^m < n < 2^(m+1), note that i(n) = i(2^m) (thanks, integer division).

answered Jan 26 '18 at 08:05

torbonde

2,459
1
15
17

1

IMO you don't explain what the OP doesn't understand: how to estimate the number of iterations. – Jan 26 '18 at 08:10
"consider the number of iterations for n = 2^m, for some m, and compare this number with log_2(n)". Granted, I don't give the answer, but I do tell how to arrive at it. Give a man a fish, and all that. – torbonde Jan 26 '18 at 08:40
Mh, this amounts to the initial question, doesn't it ? – Jan 26 '18 at 11:22

score 1 · Answer 3 · answered Jan 26 '18 at 08:13

You repeatedly divide n by two until you reach 1 or less. Therefore your stop condition is (roughly) expressed by the equation n/2^k = 1 <=> n = 2^k <=> log_2 n = k ( / is an integer division in your code). Roughness is allowed because we are dealing with O( ) and constants will disappear anyway.

Why is the time complexity O(log n)?

3 Answers3