Big-O notation describes how an algorithm's running time or memory use grows as the input size increases. This cheat sheet helps students compare common growth rates and recognize which algorithms scale well. It is useful when choosing data structures, analyzing code, or explaining why one solution is faster than another for large inputs.
Key Facts
- O(1) is constant time, meaning the number of steps stays about the same as n grows.
- O(log n) is logarithmic time, often seen when the input is repeatedly cut in half, such as binary search.
- O(n) is linear time, meaning the work grows directly with input size n.
- O(n log n) is common for efficient comparison sorting algorithms such as merge sort and heapsort.
- O(n^2) is quadratic time, often caused by two nested loops that each depend on n.
- O(2^n) is exponential time, often seen in brute-force algorithms that try every subset or combination.
- O(n!) is factorial time and usually becomes impractical very quickly as n increases.
- When simplifying Big-O, drop constants and lower-order terms, so O(3n^2 + 10n + 5) becomes O(n^2).
Vocabulary
- Big-O notation
- Big-O notation is a way to describe the upper-bound growth rate of an algorithm as input size increases.
- Input size
- Input size, usually written as n, is the amount of data an algorithm must process.
- Time complexity
- Time complexity describes how the number of operations in an algorithm grows as n changes.
- Space complexity
- Space complexity describes how the amount of memory used by an algorithm grows as n changes.
- Dominant term
- The dominant term is the part of a formula that grows fastest and determines the Big-O class.
- Nested loop
- A nested loop is a loop inside another loop, often multiplying the total number of operations.
Common Mistakes to Avoid
- Keeping constants in the final Big-O answer is wrong because Big-O focuses on growth rate, so O(4n) simplifies to O(n).
- Adding loop complexities when loops are nested is wrong because nested loops usually multiply, so n loops inside n loops gives O(n^2).
- Assuming O(n^2) is always bad is misleading because it may be acceptable for small inputs, but it scales poorly for large inputs.
- Confusing O(log n) with O(n) is wrong because logarithmic algorithms grow much more slowly by reducing the problem size each step.
- Judging an algorithm only by Big-O can be incomplete because constants, hardware, input patterns, and implementation details also affect real performance.
Practice Questions
- 1 Simplify the complexity expression O(6n^2 + 20n + 100).
- 2 An algorithm checks every pair of items in a list of n items. What is its likely Big-O time complexity?
- 3 If binary search starts with 1024 sorted items and cuts the search space in half each step, about how many steps are needed in the worst case?
- 4 Explain why an O(n log n) sorting algorithm is usually preferred over an O(n^2) sorting algorithm for very large lists.
Understanding Big-O Comparison Chart
Big-O is not a stopwatch reading. It is a model for predicting what happens when a problem becomes much larger. Real running time depends on the computer, programming language, compiler, and input details.
Big-O ignores those details to focus on the shape of growth. It usually describes an upper limit, often the worst case.
A search through an unsorted list may find an item immediately, yet it may need to inspect every item when the target is last or missing. That worst case matters when software must remain reliable for every user.
The data structure behind a program can change its growth rate dramatically. Reading one item from an array by its position takes about the same amount of work regardless of array length. Finding a value in an unsorted array requires checking items one by one.
Binary search is much faster for large collections, but it only works when the data is already sorted. Hash tables can often find a stored value in near constant time, though poor hashing or many collisions can make them slower. Big-O therefore helps students connect code choices with the way data is organized.
Growth rates become clearer when input size doubles. A linear task takes roughly twice as much work. A quadratic task takes roughly four times as much work because many more pairs must be considered.
For an exponential task, doubling the input can multiply the work by an enormous amount. This is why a brute-force solution may appear fine on ten items but fail on forty items.
Real examples include comparing every pair of students in a class, checking duplicate entries in a spreadsheet, sorting a large contact list, and trying possible schedules or password combinations. Small test cases can hide serious scaling problems.
When analyzing code, count how often the important operation can run. A loop inside another loop is not automatically quadratic. If the inner loop runs only a fixed number of times, the total work can still be linear.
If one loop shortens as another grows, add the actual counts instead of guessing. Recursion needs the same care. Ask how many recursive calls are created and how much work each call performs.
Keep time complexity separate from space complexity, since an algorithm can run quickly while using a large amount of memory. In classwork, state what the input size represents, identify the dominant work, then explain why smaller terms stop mattering for very large inputs.