CODEWITHSUNDEEP
algorithmloggingbig-oanalysis
coolcskid94
coolcskid94

Reputation: 25

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

Upvotes: 2

Views: 85

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

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)

Upvotes: 3

Related Questions