OCR AS Level Computer Science big O notation

The algorithm for a bubble sort of n items is given below.

for i = 1 to n-1

for j = 1 to (n-i)

if numbers [j] > numbers[j+1]

# Swap the names in the array

temp = numbers[j]

numbers[count] = numbers[count+1]

numbers[count+1] = temp

endif

next j

next i

(a) Calculate the number of steps needed to sort a list of 5 items. Count the IF statement in the inner loop as one statement. [2]

I don't know how to do this. What exactly is a 'step'? Thank you

Its possibly a bit loosely worded, but for 2 marks, Id presume they mean that the code block associated with the conditional if is "1 step", irrespective of whether the body is executed or not, so really youre just counting the number of iterations in the nested for loops.

Thank you. So it would be 5 steps?

There are 2 loops, and how many times does each one execute its body? As a trivial case, how many times would a bubble sort execute if there were 2 elements in the list?

Would it be 10? If there were 2 elements, would it be 4?

No for both. Do you understand how two nested loops operate and how many times each executes?
A bubble sort for 2 elements would be "trivial" if you understand the algorithm.

Okay. I'll try to break everything down.
Why is it to n-1 and not n in:
for i = 1 to n-1

And why is it to (n-i)?
for j = 1 to (n-i)

My eyes are going, the inner loop goes to n-i, not n-1. So 10 is right (though 4 wasnt if there are 2 elements), do you know how you came up with that and how the inner/outer loops work?

I'm not sure... but is it because the innor loop checks if the number is bigger than the next number and if it is, it swaps the number. And then the outer loop goes through the list?? This is confusing to me. And what is [count] for? Is it to count the number of swaps we make?

If you're wondering why I find this so confusing it's because I didn't take cs for my GCSEs.

You do cover bubble sort on your gcse, so you may need to google some vidoes/basic tutorials - its relatively straight forward. But even if you don't understand the algorithm, n is 5, so
* The outer loop operates 4 times so i=1..(5-1)
* The first time the inner loop iterates *** times as j=1..(5-1)
* The second time the inner loop iterates *** times as j=1..(5-2)
* ...

But you are expected to know how the bubble sort operates, so a quick google would be worthwhile.