CODEWITHSUNDEEP
c++algorithm
Tom
Tom

Reputation: 13

How can we compute the time complexity of the below function

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.

Upvotes: 0

Views: 107

Answers (2)

user1196549
user1196549

Reputation:

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.

Upvotes: 1

Dimanshu Parihar
Dimanshu Parihar

Reputation: 377

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)

Upvotes: 0

Related Questions