Big O complexity in recursive method

Question

For f(n) = f(n/2) + 1 where n is power of 2 (n >= 2),

with f(1) = 1,

Is it going to be

f(n) = O(logn),
f(n) = O(loglogn),
or
f(n) = O(sqrt(logn))

I believe its the first one but I am not sure how to verify.

Answer 1

two approaches:

(1) you can use induction:

Let's say O(logn) is correct, then we should show:

---> for n=1: it is true => f(2) = f(1) + 1 = 1 (f(1) is zero because n>=2) so, it is constant and o(log2) = o(1)

---> IF it is true for n, then it should be true for the next value (which is 2n since n is a power of two):

So, we assume O(logn) is true for f(n) = f(n/2) + 1

Now, we should see if it is still true for:

f(2n): f(2n) = f(n) + 1 => O(log2n) = O(logn) + 1

So, we can see it is again true. Because, for large n, we have:

Left_side_of_equation: O(log2n)=O(logn + 1) = O(logn)

Right_side_of_equation: O(logn)+1 = O(logn)

===============================================

(2) binary search trees concept:

If you know about binary search trees, then this formula shows the computing time of an algorithm that can be based on binary search tree. So, the computing time of each layer depends on its child layer (I mean a layer under it). And, at each layer, the computing time that is being added is O(1). SO, in Binary Search Tree, since you have Logn layers, in total you will have: Logn * o(1) complexity which is O(logn).

Answer 2

If n is a power of 2, we can write n = 2^m. The recurrence reads

f(2^m) = f(2^(m-1)) + 1

which can be seen as

g(m) = g(m-1) + 1

with g(0) = 1.

It is no big deal to see that

g(m) = m + 1

which implies

f(n) = log2(n) + 1.

This is the exact solution.