Big O notation describes how fast the number of operations grows as the input gets larger. Comparing every pair among values takes comparisons, and in Big O this count is written , read "order squared". We kept the term that grows fastest, , and dropped the constant in front of it.
Growth when the input doubles
The constant in front can be dropped because it does not change how the count reacts when the input grows. When doubles, a count proportional to doubles and a count proportional to is multiplied by four, whatever the constant is:
So an program that takes one second on 10,000 values takes about four seconds on 20,000 and about 100 seconds on 100,000. The constant depends on the machine, the language and what we chose to count as one operation. The growth depends only on the algorithm. A faster computer makes every step quicker by the same factor, so on a judge, on our laptop or on a phone, this program takes four times as long when doubles.
Count the turns of the inner loop
To count the work of a loop inside a loop, we add up the turns of the inner loop over every turn of the outer one. Take five values that are all different, and compare each value with every value before it. The value at position 0 has nothing before it. The value at position 1 is compared with one earlier value, the value at position 2 with two, and so on up to position 4, whose value is compared with four. That makes comparisons, one for each pair of positions.
For different values the pattern is the same: the value at position is compared with the values before it. Adding these up gives the total number of comparisons:
With this is , the ten cells of the figure. With , the largest list in Distinct Numbers, it is , about twenty billion comparisons.