Search code examples
algorithmloggingbig-oanalysis

How to Perform Algorithm analysis

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(n2)..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
Solution

  • 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)