Thinking in Algorithms
How to turn a problem into exact steps, and why some step-by-step methods are millions of times faster than others. Play a guessing game against a computer, watch a sort happen, and write your first algorithms.
Start this course →Lessons
- 1What makes a good algorithmTurn a vague task into exact, ordered steps.6 min
- 2Searching: one by one, or halve itCompare two ways of finding something, and see why one wins.7 min
- 3Sorting: putting things in orderWatch a sorting algorithm work, step by step.6 min
- 4How fast is fast?Describe how an algorithm's work grows as its input grows.6 min
What you will learn
- An algorithm takes an input, follows exact steps, and produces an output.
- Good steps are exact, ordered and finish.
- Decomposition breaks a hard problem into easy pieces.
- Linear search checks items one at a time and works on any list.
- Binary search halves the possibilities each step, but needs sorted data.
- For 1,000,000 sorted items, binary search needs at most 20 checks.
- Sorting puts items in order, which makes fast searching possible.
- Bubble sort compares neighbours and swaps them when they are out of order.
- Bubble sort is easy to understand but slow on large lists; faster methods exist.
- Efficiency asks how the work grows as the input grows.
- Linear time grows in step, logarithmic time barely grows, quadratic time explodes.
- Big O notation is shorthand for these growth patterns: O(n), O(log n), O(n²).
Terms explained in this course
- decomposition
- Breaking a big problem into smaller problems that are each easy to solve.
- pseudocode
- Steps written in plain language, laid out like a program but not in any real programming language.
- search algorithm
- A method for finding an item in a collection.
- linear search
- Checking items one at a time, from the start, until the one you want turns up.
- binary search
- Searching a sorted collection by checking the middle item, then throwing away the half that cannot contain the answer, again and again.
- sorting
- Putting items in order, such as smallest to largest or A to Z.
- bubble sort
- A simple sorting method that repeatedly compares neighbouring items and swaps them if they are in the wrong order.
- efficiency
- How much time or memory an algorithm needs, especially as the input grows.
- big o notation
- A short way of describing how an algorithm's work grows with the size of its input, such as O(n) or O(log n).
- linear time
- Work that grows in step with the input: twice the data, twice the work. Written O(n).
- logarithmic time
- Work that grows very slowly: doubling the data adds only one more step. Written O(log n).
- quadratic time
- Work that grows with the square of the input: twice the data, four times the work. Written O(n²).