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

Find more quizzes: