Data structures and algorithms 0/7

DSA, Basics

What is Big O notation?

Also called asymptotic notation, order of growth

392 words · 2 min read

Big O notation describes how fast the number of operations grows as the input gets larger. Comparing every pair among nn values takes n(n−1)/2=n2/2−n/2n(n-1)/2 = n^2/2 - n/2 comparisons, and in Big O this count is written O(n2)O(n^2), read "order nn squared". We kept the term that grows fastest, n2/2n^2/2, and dropped the constant 1/21/2 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 nn doubles, a count proportional to nn doubles and a count proportional to n2n^2 is multiplied by four, whatever the constant is:

3n  →  3⋅(2n)=2×3n12n2  →  12(2n)2=4×12n2\begin{aligned} 3n \;&\to\; 3 \cdot (2n) = 2 \times 3n \\ \tfrac{1}{2} n^2 \;&\to\; \tfrac{1}{2} (2n)^2 = 4 \times \tfrac{1}{2} n^2 \end{aligned}

So an O(n2)O(n^2) 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 nn 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 0+1+2+3+4=100 + 1 + 2 + 3 + 4 = 10 comparisons, one for each pair of positions.

Each checked cell (i,j)(i, j), with i<ji < j, is one comparison of the value at position jj with the earlier value at position ii. Column jj holds the jj comparisons made for position jj, the 0, 1, 2, 3 and 4 of the text. The figure adds the same ten cells by rows instead, as 4+3+2+1+04 + 3 + 2 + 1 + 0.

For nn different values the pattern is the same: the value at position kk is compared with the kk values before it. Adding these up gives the total number of comparisons:

0+1+2+⋯+(n−1)=n(n−1)20 + 1 + 2 + \dots + (n - 1) = \frac{n(n-1)}{2}

With n=5n = 5 this is 5×4/2=105 \times 4 / 2 = 10, the ten cells of the figure. With n=200,000n = 200{,}000, the largest list in Distinct Numbers, it is 19,999,900,00019{,}999{,}900{,}000, about twenty billion comparisons.

Time complexity Describe how an algorithm’s work grows, count its operations, and use input limits to compare approaches. Read the full lesson