Algorithm analysis

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 :slight_smile:

thank you sir…no problem with your english it is beautiful…

@I_lOve_tanyaromanova O(1) really…:slight_smile:

1 Like