Project ForgeSign up free
Algorithms
Complexity Analysis
GATE 2007
Expert

What is the time complexity of the following recursive function:

int DoSomething(int n) {
  if (n <= 2)
    return 1;
  else
    return (DoSomething(floor(sqrt(n))) + n);
}
  • AΘ(n²)
  • BΘ(n log₂ n)
  • CΘ(log₂ n)
  • Θ(log₂ log₂ n)

Explanation

Time complexity counts the NUMBER of operations (recursive calls), not the returned value's magnitude. The recursion depth follows T(n)=T(√n)+O(1). Substituting k=log₂n turns this into T(k)=T(k/2)+O(1), which solves to Θ(log k) = Θ(log₂ log₂ n).

Source: GATE CS 2007 (2007)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free