Explaining why this algorithm is n^2

Question

I'm having some trouble argumenting for the runtime of this code. I know the code runs at O(n^2), but I've been told to explain why it does. I figured I need to do some calculations on it but I'm stuck. The algorithm (Pseudo code) I need to figure out is.

    count = 0                        1
    for i = 0 to n-2                 n
        for j = 1 to n               n^2
            if A[j]<A[i]             1
                count = count + 1    1

I've written what I think is the runtime of each line as well. However, I don't know if this is correct.

I've been told to explain why the algorithm runs at O(n^2). So what confuses me is how I'm suppose to write it, how do I go from what I have to the answer O(n^2) — wardz, Sep 30 '18 at 10:22

score 1 · Answer 1 · answered Sep 30 '18 at 10:42

outer for loop traverses from 0 to n-2

Removing constants in outer loop, we could say it will loop for n times. for each number in the range [0..n-2] in outer loop, inner loop iterates from [1..n]

if i=0, inner loop runs from 1 to n,
if i=1, inner loop runs from 1 to n,
.
.
.
till  i=n-2, inner loop runs from 1 to n,

so time complexity would be (outer loop * inner loop) = O(n*n) which is O(n^2)

score 0 · Answer 2 · answered Sep 30 '18 at 10:37

The outer for loop iterates exactly n-1 = O(n) times. On each iteration of the outer for loop, the inner for loop iterates exactly n = O(n) times, so overall it iterates O(n^2) times. The work done inside the inner loop is constant time, O(1). Therefore, the overall time complexity is O(n^2), since we repeated O(1) amount of work O(n^2) times.

Explaining why this algorithm is n^2

2 Answers2