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 ?
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.
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))
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.
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.
