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;
}
$\theta(n^2)$
$\theta(nlogn)$
$\theta(n)$
$\theta(logn)^2$
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)$
The function has a nested loop: the outer loop runs i from 0 to n-1 (n iterations), and for each i, the inner loop runs j from i down to 1, executing i times. Total iterations = sum of i for i=0 to n-1 = n(n-1)/2, which is O(n^2). This is a classic triangular/arithmetic series pattern, so the time complexity is theta(n^2), not linear, logarithmic, or n log n — those growth rates would require the inner loop to be independent of n or shrink geometrically, which isn't the case here since the inner loop bound grows linearly with the outer index.