Alorithmic complexity of recursive function

Question

Here is my function. It is a simple one, I'm just not confident on what the answer is.

  int calcul( int n) {
    if(n=1)
      return 1;
    else
      return calcul(n/2) + 1;
  }

Now, to get the complexity, I do:

T(n) = T(n/2) + O(1)

T(n/2) = T(n/4) + O(1)

...

T(1) = O(1)

Now, adding the equations, I'm getting

T(n) = O(1) + O(1)...

so what is the final answer ?

Answer 1

You're executing the function once for each time you can divide n by 2, which is log n times.

So you get O(log n).

Edit:

The logarithm (of base 2) of a number n is the power 2 has to be raised to get n.

That is, 2^(log n) = n, where ^ indicated exponentiation.

Now, a simple way to calculate an approximation of log n is divide n by 2 while n > 1.

If you've divided k times, you get n < 2^k.

Since k - 1 divisions still yielded n > 1, you also have n >= 2^(k-1).

Taking logarithms on each member of 2^(k - 1) <= n < 2^k, you get k - 1 <= log n < k.

Answer 2

The algorithm is very similar to http://en.wikipedia.org/wiki/Binary_search_algorithm

So, you could read detailed explanations why it's O(log(n))

Answer 3

I suggest becoming familiar with the Master theorem. In this case, a=1, b=2 and f=O(1). Since such that f = Theta(1) = Theta(n^(log_2(1) log^k n) = Theta(log^k n) for k = 0, we are in the second case of the theorem and T(n) = Theta(log^(k+1) n) = Theta(log n).

Very handy theorem, and useful in cases when comparing to other algorithms and doing other kinds of analyses aren't so easy.

Answer 4

The thing is that Every time your input is divided by 2 till it satisfies condition. ex. n/2, n/4, n/8....n/n

Suppose you have input as 8, then this log 8 base two will be 3. So O(logn). Constant should not be counted.

Hope it helps.