Last Updated : 16 May, 2019
What is the time complexity of fun()?
C
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;
}
(A)
Theta (n)
(B)
Theta (n2)
(C)
Theta (n*log(n))
(D)
Theta (n*(log(n*log(n))))
Answer: (B)
Explanation:
The time complexity can be calculated by counting the number of times the expression “count = count + 1;” is executed. The expression is executed 0 + 1 + 2 + 3 + 4 + …. + (n-1) times.
Time complexity = Theta(0 + 1 + 2 + 3 + .. + n-1) = Theta (n*(n-1)/2) = Theta(n2)
Quiz of this Question
Please comment below if you find anything wrong in the above post
Like Article
Suggest improvement
Share your thoughts in the comments
