An algorithm is a step-by-step method for solving a problem, and Big-O notation describes how the amount of work grows as the input size increases. This matters because two programs can both be correct but have very different speeds for large inputs. Instead of timing a program on one computer, Big-O focuses on the growth pattern of the number of steps.
It helps programmers and mathematicians compare efficiency in a general way.
Key Facts
- Big-O describes an upper bound on growth: f(n) = O(g(n)) means f(n) grows no faster than a constant multiple of g(n) for large n.
- Common growth rates from fastest to slowest are O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), and O(n!).
- Constant factors are ignored in Big-O, so 5n + 20 = O(n).
- Lower-order terms are ignored for large n, so n^2 + 100n + 7 = O(n^2).
- A loop that runs n times is usually O(n), while nested loops that each run n times are usually O(n^2).
- Binary search on a sorted list has runtime O(log n), while linear search has runtime O(n).
Vocabulary
- Algorithm
- An algorithm is a precise sequence of steps used to solve a problem or complete a task.
- Input size
- Input size is the amount of data an algorithm processes, often represented by n.
- Runtime
- Runtime is the number of steps or amount of time an algorithm needs to finish.
- Big-O notation
- Big-O notation describes how an algorithm's runtime or memory use grows as input size becomes large.
- Asymptotic growth
- Asymptotic growth is the long-term growth behavior of a function as n becomes very large.
Common Mistakes to Avoid
- Keeping constant factors in the final Big-O answer is wrong because Big-O focuses on growth rate, so O(3n) should be written as O(n).
- Keeping lower-order terms is wrong because they become less important for large inputs, so O(n^2 + n) should be simplified to O(n^2).
- Assuming every loop means O(n) is wrong because a loop can run a fixed number of times, n times, log n times, or depend on another variable.
- Comparing algorithms only using small input sizes is misleading because slower growth rates often become much better only when n is large.
Practice Questions
- 1 An algorithm takes 4n + 12 steps. What is its Big-O runtime, and how many steps does it take when n = 50?
- 2 An algorithm uses two nested loops, and each loop runs from 1 to n. How many total inner-loop operations occur when n = 100, and what is the Big-O runtime?
- 3 A sorted list contains 1,000,000 items. Explain why binary search is usually more efficient than linear search for finding one item.