What is the time complexity of the following recursive function: int…
2007
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.
Θ(nlogn)
- C.
Θ(logn)
- D.
Θ(loglogn)
Attempted by 95 students.
Show answer & explanation
Correct answer: D
Step 1: Track the value of n at each step
In every recursive call, the value of n is replaced by its square root. Let's look at how n changes over successive calls mathematically using exponents:
Initial value: n = n1
After 1st call: sqrt(n) = n1/2
After 2nd call: sqrt(sqrt(n)) = (n1/2 )1/2= n1/4 = n1/2^2
After 3rd call: n1/8 = n1/2^3
After $k$ calls: The value of n becomes n1/2^k
Step 2: Set up the termination condition
The recursion stops when this diminishing value finally reduces down to the base case, which is approximately 2.
So, let's assume the function terminates after $k$ steps. We can write this as an equation:
n1/2^k = 2
Now, our goal is to solve for k (the number of steps) because the number of steps directly represents the time complexity.
Step 3: Solve for k using Logarithms
To get k out of the exponent, we take the logarithm (base 2) on both sides:
log_2(n1/2^k) = log_2(2)
Using the logarithm property log(ab) = b.log(a), we can pull the exponent to the front:
(1/2k ).log_2(n) = 1
Now, multiply both sides by 2k to isolate it:
log_2(n) = 2k
To isolate k completely, we need to take the logarithm (base 2) a second time:
log_2(log_2(n)) = log_2(2k)
Using the same exponent property (log_2(2k) = k.log_2(2) = k.1):
k = log_2(log_2(n))
Conclusion
Since the total number of recursive calls k is exactly log_2(log_2(n)), and each individual call executes in constant O(1) time (performing basic arithmetic like square root and addition), the overall time complexity is:
Time Complexity = O(log log n)