Algorithms, Data Structures

In our phone, we have a list of alphabetized names with numbers attached to them that we can search through.

On our first day, we had three algorithms: searching one page at a time, searching two pages at a time but checking the last page once we’ve past the name we’re looking for, and finally binary search where we eliminate half the problem at each step.

Recall that the running times look like this for each algorithm:

Binary search has running time of log n, and this is denoted by the big O symbol, O.

For example, our first algorithm of searching one page at a time has running time O(n) ("big O of n"), where n is the size of the problem (number of pages, in our case) and big O is the upper bound, or worst case, of the number of steps required for the algorithm. In this case, since we are searching one page at a time, with n pages we will require n steps.

In the second case, we will have O(n / 2), but we generally ignore the constants, since fundamentally the efficiency of the algorithm isn’t much better. In the real world, the second algorithm is certainly twice as fast, but theoretically the growth in running time is still linear to n, so we simplify them to be equivalent.

In the last case, the running time is O(log n), since the number of steps we need is logarithmic to the number of pages in our phone book.

In Scratch, we can nest three repeat blocks with 10s to do something 1000 times:

But if we were to repeat on n, the number of times would be n^3:

With O(n³), an algorithm becomes very slow very quickly as n gets large.

Ω, Omega, is also used sometimes to denote the lower bound of an algorithm, though this is less useful since it describes the best case.

For all of our algorithms, the Ω running time is 1, since the name we are looking for might be on the first page we look at!

There are lots of formulas that might be possible for O, with common ones like:

An algorithm that takes a constant number of steps, with O(1), might be one that does something a certain number of times.

If an algorithm’s upper bound is the same as its lower bound, then it also has a Θ, theta.

We have a volunteer try to find the number 50 behind 8 sheets of paper, knowing nothing else, and that resulted in randomly flipping over the papers. This has a worst case, O(n) steps if there are n papers, and a best case Ω(1), if we got lucky and found the number in the first try.

Now we have sorted numbers, and by using binary search we had O(log n).

But there was work done in the beginning, to sort the numbers the first time.

Let’s say we have the following numbers:

4  2  7  5  6  8  3  1

We can compare numbers next to each other, and swap them:

4  2  7  5  6  8  3  1
2  4  7  5  6  8  3  1

Then we keep going:

2  4  7  5  6  8  3  1
2  4  7  5  6  8  3  1
2  4  5  7  6  8  3  1

When we get to the end of the row, we have:

2  4  5  6  7  3  1  8

So we need to do this process n more times, since 8 is now all the way to the right, but we need to finish moving all the other numbers. And each time we go through the row, we look at n - 1 pairs of numbers, which simplifies to a running time of n². This algorithm is called bubble sort.

We can try a different algorithm. Each time, we’ll find the smallest number in the list, and swap it with the number at the beginning of the list:

4  2  7  5  6  8  3  1
1  2  7  5  6  8  3  4

We need to make this a swap, and not just move the 1 to somewhere before the 4, since in memory our numbers might be stored between other variables, and using the memory before the 4 to store the 1 might result in overwriting something else.

We’ll repeat this with the rest of the list until it’s completely sorted, but finding the smallest element each time takes n steps, and there are n elements to move, so the running time is n² again. And this algorithm is called selection sort.

The pseudocode might look like this:

for i from 0 to n-1
    find smallest element between i'th and n-1'th
    swap smallest with i'th element

And for bubble sort:

repeat until no swaps
    for i from 0 to n-2
        if i'th and i+1'th elements out of order
            swap them

In both cases, i is the index in the list, and since we start with index 0, we go up to n - 1 or, in the case of bubble sort, the n - 2th element (the second to last element, since we compare it to the last element).

To calculate the running time of these algorithms more precisely, we’ll consider the number of steps.

If we have a list with n elements, we would compare (n - 1) pairs in our first pass.

And after our first pass, the largest element will have been swapped all the way to the right. So in our second pass, we’ll only need (n - 2) comparisons.

By the end, we’ll have made a total of (n - 1) + (n - 2) + …​ + 1 comparisons. And this one actually adds up to n(n - 1)/2. And that multiplies out to (n² - n)/2.

When comparing running time, we generally just want the term with the biggest order of magnitude, since that’s the only one that really matters when n gets really big. And we can even get rid of the factor of 1/2.

We can look at an example (not a proof!) to help us understand this. Imagine we had 1,000,000 numbers to sort. Then bubble sort will take 1,000,000²/2 - 1,000,000/2 steps, and if we multiply that out, we get 500,000,000,000 - 500,000 = 499,999,500,000. Which is awfully close to just the first number.

So when we have an expression like (n² - n)/2, we can say it is on the order of, O(n²).

And we can visualize different sorting algorithms with sites like https://www.cs.usfca.edu/_{galles/visualization/ComparisonSort.html[https://www.cs.usfca.edu/}galles/visualization/ComparisonSort.html] or https://www.toptal.com/developers/sorting-algorithms.

Merge sort, one other algorithm, divides the list of numbers in half over and over and sorts them individually before merging them, leading to a fundamentally better running time of O(n log n).

Another fun animation has sound to help with visualizing the sorting.