How to Perform Algorithm analysis

Question

I have the following algorithm and need to conduct a Big O analysis on it. I'm very new to this topic but I understand O(1), O(n), O(n²)..O(log n) and O(n log n).

How would I analyze the following algorithm?

x <== 1
for i = 1 to n
    for j = i to 1 (decrement)
        x <== x + 1

check: this http://stackoverflow.com/a/13622284/1673391 "edit" part, similar trick you can apply. — Grijesh Chauhan, Feb 03 '15 at 07:35
@Grijesh yea, i see that…but would the decrementation make a difference or is the run time in this case also O(n^3) as well — coolcskid94, Feb 03 '15 at 07:38
Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Paul Hankin, Sep 10 '17 at 10:12

score 3 · Accepted Answer · answered Feb 03 '15 at 08:05

3

For each execution of the inner loop: for j = i to 1, it will run i steps, with i from 1 to n.

So the total time complexity is

1 + 2 + ... + n = n*(n+1)/2 ~ O(n^2)

answered Feb 03 '15 at 08:05

Pham Trung

11,204
2
24
43

How to Perform Algorithm analysis

1 Answers1