🎴 Flashcard Mode

Test on time complexity

Card1 / 8
Mastered0
Review0
QuestionClick to flip

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;
}
AnswerClick to flip back
A
$\theta(n^2)$
💡 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)$

Change Mode