What is the time complexity of this function? is it n*log(n)?

Question

I'm finding difficulty to find the time complexity of this pseudocode function

f(n):
    count = 0
    
    for (i = 0; i < n; ++i)
        for (j = i; j > 0; --j)
            count++
end;

It's not O(n) but it grows faster than O(n) and it is not O(n^2) but it grows slower than O(n^2), is it n*log(n)?

"_it grows slower than O(n^2)_": How do you come to this conclusion? — user17732522, Mar 03 '22 at 17:08
By experimenting and running the code. the inner loop execution time is growing with every loop. @user17732522 — Yousef Ali, Mar 03 '22 at 17:18
@user17732522 commented a link to a similar question. https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop — Yousef Ali, Mar 03 '22 at 17:27

score 1 · Accepted Answer · answered Mar 03 '22 at 17:10

1

The outer loop has O(n). The inner loop is also O(n), although it executes on average only half as much operations as the outer loop. But constant factors are ignored for the complexity. The complexity is thus O(n^2).

answered Mar 03 '22 at 17:10

Reinhard Männer

14,022
5
54
116

What is the time complexity of this function? is it n*log(n)?

1 Answers1