How can we compute the time complexity of the below function-CodePudding

void f(int n) 
{
 doOh(n);
 if(n<1) return;
 for(int i=0; i<2; i  )
 {
   f(n/2);
 }
}

Time complexity of doOh(n) is O(N). How can we compute the time complexity of the given function.

CodePudding user response：

Denoting the complexity as T(n), the code says

T(n) = T0 if n = 0
     = O(n)   2 T(n/2) otherwise

We can get an upper bound by replacing O(n) with c n for some c*, and we expand

T(n) = c n   2 T(n/2)
     = c n   2 c n/2   4 T(n/4) 
     = c n   2 c n/2   4 c n/4   8 T(n/8) 
     = ...

The summation stops when n < 2^l, where l is the number of significant bits of n. Hence we conclude that

T(n) = O(l c n   2^l T0) = O(l n).

*Technically, we can only do that as of n > some N. But this does not change the conclusion regarding the asymptotic behavior of T.

CodePudding user response：

Complexity = O(nlog2n)

The reason is

Every time f(n) is called, doOh(n) is called. Its time complexity is O(n) when we pass n in f(n) as you mentioned
f(n) will call f(n/2) 2 times. So time complexity will be 2*O(f(n/2)) = O(f(n/2))
f(n) is becoming f(n/2). f(n/2) is becoming f(n/4) and so on... it means this f(n) will be called log2n times (logn base 2 times).
Hence, doOh(n) will also create n n/2 n/4 and so on time complexity logn times.
n or n/2 or n/4 all have O(n) complexity. Hence the total time complexity is O(logn) * O(n) which is order of nlogn base 2 = O(nlog2n)