State gns runtime complexity int fint nifn Solution int fint

State g(n)\'s runtime complexity: int f(int n){if(n

Solution

int f(int n){
   if(n <= 1)
       return 1;
   return 1 + f(n/2);
}

int g(int n){
   for(int i=1; i<n; i *=2){
       f(i)
   }
}

Here first analyze the complexity of f():
   f() calling itself recursively with parameter n/2 each time
   Means it is dividing n by 2 in each iteration

   So, time complexity: O(logn)

No, for g():
   In g(), we have a for loop.
   We are incrementing i by doubling its current time,
   So, for loop runs logn time

   Since in each iteration f() is getting called

   So, time complexity of g() = logn * logn = (logn)^2