Big-O keeps only the shape

Computing · Algorithms & Data Structures · ages 16-17

Name ______________________ Date ____________

Which order sits between O(n) and O(n squared)?
- O(1)
- O(log n)
- O(n log n)
What is 3n + 7 in big-O form?
- O(3n + 7)
- O(n)
- O(7)
Why are constants dropped in big-O?
- Machine details, not the growth
- Constants are always zero
- Mathematicians dislike small numbers
Input doubles under an O(n squared) method. Roughly how many times the work results? Type the multiplier.
Answer: ______________
Input doubles under an O(n) method. What happens to the work?
- It stays flat
- It doubles
- It quadruples
Big-O describes an upper bound on growth for large n.
Circle one: True False
A student says O(log n) grows faster than O(n) because logs look scary. What is the error?
- Logs grow slower
- O(n) is always flat
- The two orders are identical
An O(n squared) method runs on n = 1000, then n = 2000. The constant in front is unknown. What can you still predict?
- It quadruples; k cancels
- The work stays exactly the same
- Nothing without the constant

Answer key

For grown-ups. Fold this page away before handing over the rest.

O(n log n) · The ladder runs O(1), O(log n), O(n), O(n log n), O(n squared).
O(n) · Drop the constant and the factor, leaving O(n).
Machine details, not the growth · Constants stop mattering beside growth as n gets large.
4 · Doubling n multiplies n squared by four.
It doubles · Linear work grows in step with the input.
True · It promises the work never grows faster than the named curve.
Logs grow slower · Logarithmic work adds about one step per doubling, far slower than linear.
It quadruples; k cancels · The constant scales both runs equally, so the ratio stays four.