Multiple choice time complexity of function

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)
{
    if (n <= 1) return n;
    return 2*fun1(n-1);
}

int fun2(int n)
{
    if (n <= 1) return n;
    return fun2(n-1) + fun2(n-1);
}

  1. $O(2^n)$ for both fun1() and fun2()
  2. $O(n)$ for fun1() and $O(2^n)$ for fun2()
  3. $O(2^n)$ for fun1() and $O(n)$ for fun2()
  4. $O(n)$ for both fun1() and fun2()
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

To solve this question, the user needs to know how to determine the time complexity of recursive functions based on the recurrence relation.

Let's analyze the time complexity of each function:

  • fun1(n): This function has a recurrence relation of T(n) = T(n-1) + c, where c is a constant representing the time it takes to execute the base case. By repeatedly substituting T(n-1) with T(n-2) and so on, we get T(n) = T(n-k) + kc. When the base case is reached, we have T(n-k) = 1, so T(n) = k + c. Since k is proportional to n, the time complexity of fun1(n) is O(n).

  • fun2(n): This function has a recurrence relation of T(n) = 2T(n-1) + c, where c is a constant representing the time it takes to execute the base case. By repeatedly substituting T(n-1) with 2T(n-2), 4T(n-3), and so on, we get T(n) = 2^n * T(0) + c * (2^n - 1). Since T(0) = 1, the time complexity of fun2(n) is O(2^n).

Therefore, the answer is:

The Answer is: B. O(n) for fun1() and O(2^n) for fun2().

AI explanation

fun1 makes exactly one recursive call per invocation (it just doubles the previous result), so the number of calls grows linearly with n, giving O(n) time. fun2 makes two recursive calls per invocation instead of reusing the result once, so the call tree branches at every level, doubling the work each step down and yielding O(2^n) calls overall — a classic example of how reusing versus repeating a recursive call changes complexity from linear to exponential.

Keep practicing — related questions