Calculating big O swaps, calculations, and comparisons

Question

Looking at the code below:

Algorithm sort

Declare A(1 to n)

n = length(A)

for i = 1 to n
    for j = 1 to n-1 inclusive do
       if A[i-1] > A[i] then
          swap( A[i-1], A[i] )
       end if
  next j
next i

I would say that there are:

• 2 loops, both n, n*n = n^2 (n-1 truncated to n)
• 1 comparison, in the j loop, that will execute n^2 times
• A swap that will execute n^2 times
• There are also 2n additions with the loops, executing n^2 times, so 2n^2

The answers given in a mark scheme:

Evaluation of algorithm

Comparisons

The only comparison appears in the j loop. Since this loop will iterate a total of n^2 times, it will execute exactly n^2

Data swaps

• There may be a swap operation carried out in the j loop.
• Swap( A[i-1], A[i] ) Each of these will happen n^2 times.
• Therefore there are 2n^2 operation carried out within the j loop
• The i loop has one addition operation incrementing i which happens n times
• Adding these up we the number of addition operations which is 2n^2 + n
• As n gets very big then n^2 will dominate therefore it is O(n^2)

NOTE: Calculations might include assignment operations but these will not affect overall time so ignore

Marking overview:

• 1 mark for identifying i loop will execute n times.
• 1 mark for identifying j loop will execute 2n^2 times Isn't this meant to be n*n = n^2? For i and j
• 1 mark for correct number of calculations 2n^2 + n Why is this not +2n?
• 1 mark for determining that the order will be dominated by n^2 as n gets very big giving O(n^2) for the algorithm

Edit: As can be seen from the mark scheme, I am expected to count:

• Loop numbers, but n-1 can be truncated to n
• Comparisons e.g. if statements
• Data swaps (counted as one statement, i.e. arr[i] = arr[i+1], temp = arr[i], etc. are considered one swap)
• Calculations
• Space - just n for array, etc.

Could someone kindly explain how these answers are derived?

Thank you!

Answer 1

Here's my take on the marking scheme, explicitly marking the operations they're counting. It seems they're counting assignments (but conveniently forgetting that it takes 2 or 3 assignments to do a swap). That explains why they count increment but not the [i-1] indexing.

Counting swaps

i loop runs n times
    j loop runs n-1 times (~n^2-n)
        swap (happens n^2 times)            n^2

Counting additions (+=)

i loop runs n times 
    j loop runs n-1 times (~n^2)
        increment j (happens n^2 times)     n^2
    increment i (happens n times)           n

sum:                                        2n^2 + n