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);
}
time complexity of function

  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()

Show answer
Correct Option: B
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().

Find more quizzes: