Programming algorithms

How an algorithm's work grows as the data grows — the shape of the growth, not the time in seconds, which depends on the machine it runs on.

Count the loops over the data. No loop is O(1), one loop is O(n), a loop inside a loop is O(n²), and halving what is left at each step is O(log n).

Big O describes the shape of the growth, and constants and lower-order terms do not change that shape. Doubling the data still doubles the work.

Time complexity is how the number of steps grows; space complexity is how the extra memory grows, not counting the input. Bubble sort is O(n²) time but O(1) space, because it sorts in place.

Twice the data means four times the work, and ten times the data means a hundred times. At 1,000 items that is a million steps; at 10,000 it is a hundred million.

It checks each item in turn until it finds the target or runs out, returning the position or -1. Best case O(1) if the target is first, worst case O(n) if it is last or absent.

Look at the middle item. If it equals the target, stop. If it is too small the target is to the right, so move low to mid + 1; if too big, move high to mid - 1. Each step discards about half the remaining list.

Discarding half depends on knowing which half the target would be in, which only holds if the list is in order. On unsorted data it does not run slowly — it returns the wrong answer.

When low passes high, meaning there is nothing left to search. It then returns -1 to indicate the target is absent.

Doubling the list doubles linear search's worst case, but adds only one comparison to binary search's. Sixteen items need at most four binary comparisons; a million need about twenty.

It compares each neighbouring pair and swaps any that are out of order. Each pass sends the largest remaining value to the end, so the next pass can compare one fewer pair.

For each position it looks through the whole remaining list, remembering where the smallest value is, then swaps it into place. At most one swap per position.

Both make O(n²) comparisons. Bubble sort makes up to O(n²) swaps; selection sort makes only O(n). Bubble sort has a best case of O(n) on sorted data thanks to its early exit, while selection sort has none.

Both are O(1). Each sorts in place, needing only a couple of extra variables however large the list becomes.

When writing data is far more expensive than reading it. The comparison counts are identical, so the algorithm doing O(n) swaps instead of O(n²) is clearly better.