Tag: time complexity of function

Questions Related to time complexity of function

What is time complexity of fun()?

int fun(int n)
{
  int count = 0;
  for (int i = 0; i < n; i++)
     for (int j = i; j > 0; j--)
        count = count + 1;
  return count;
}
time complexity of function

  1. $\theta(n^2)$

  2. $\theta(nlogn)$

  3. $\theta(n)$

  4. $\theta(logn)^2$

Show answer
Correct Option: A
Explanation:

To solve this question, the user needs to know the concept of time complexity and how to analyze the time complexity of a given algorithm.

The given function fun() contains two nested loops that iterate over the range of n and j respectively. The outer loop runs n times, and the inner loop runs from i to 1. Therefore, the total number of iterations is the sum of the first n positive integers, which is n*(n+1)/2.

Since the number of iterations is proportional to n^2, the time complexity of the function is $\theta(n^2)$.

Therefore, the correct answer is:

The Answer is: A. $\theta(n^2)$

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