Derive how this is bigO expression Olog2n giving n a value w

Derive how this is bigO expression O(log2n) giving n a value. while (n > 1) {k + n * 3; n = n/z;}

Solution

Given:

while(n > 1)

{

k += n * 3;

n = n / 2;

}

The loop starts with n value, and will continue till n value less than or equal to 1.

Assume n = 2^m.

Now, every time the loop runs, m value is reduced by 1.

So, the loop continues for values: 2^m, 2^m-1, 2^m-2, 2^m-3, ... , ... ... ... , 2^m-m. This means, the loop runs for m times. Therefore, the efficiency of the above algorithm is: O(m). As, you want the answer in terms of n,

n = 2^m. So, m = log₂n.

Therefore, the given algorithm efficiency is: O(log₂n).