Search code examples
algorithmrecursionbig-ocomplexity-theorylogarithm

Big O complexity in recursive method

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.

Solution

  • 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.