Hello,i am not able to get why this code snippet has complexity O(n)
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;
}
What i think its complexity should be O(n log n*log n)*.Can anybody please explain me this in detail what is its time complexity?
Of course, it is O(n^2). At first iteration of i j will do 1 operation, at the second 2 operation …
and at the last n operation. All time is (1 + 2 + 3… + n) = n*(n+1)/2. This is O(n^2). Sorry for my bad English.
It is O(N^2), as explained above. However, most modern compilers will optimize it to run in O(1), when optimization is turned on 
thank you sir…no problem with your english it is beautiful…
@I_lOve_tanyaromanova O(1) really…