Learn
A reading path through the site, from the first ideas to the core algorithms.
This path goes through the site in an order that works for most readers. Each page comes after the pages that it needs. Start at the top. If you know a page already, skip it.
First steps
- Asymptotic notation · definition
The notations O, Ω and Θ compare the growth of two functions for large inputs and ignore constant factors.
- Comparison model · model
A model where an algorithm learns about its input only by comparing two items. The cost is the number of comparisons.
- Loop invariant · concept
A statement about the variables of a loop that is true before each step. It is the main tool to prove that a loop is correct.
- Search in a sorted array · problem
Given a sorted array and a key, find an index of the key, or report that the key is not in the array.
- Sorting · problem
Put the items of a sequence in non-decreasing order by a key.
- Binary search · algorithm
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- Insertion sort · algorithm
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- Merge sort · algorithm
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.