Big-O Comparison Chart Cheat Sheet

A printable reference covering Big-O notation, growth rates, complexity comparisons, common algorithm classes, and input size scaling for grades 9-12.

Download PNG

Related Tools

Related Labs

Related Worksheets

Related Infographics

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.

Sign in to save