Growth with input size n · illustrative scale
work
1
2
3
4
Common classes · typical example
O(1) — array index / hash lookup* O(log n) — binary search O(n) — scan every item
O(n log n) — efficient comparison sort O(n²) — all pairs / simple nested loops O(2ⁿ) — try every subset
Quick rules for analyzing code
• Sequential parts: add, then keep the dominant term. O(n) + O(n²) = O(n²) • Nested n-sized loops: multiply → O(n²). • Repeated halving: count halvings → O(log n). • Recursion: count levels and work per level; account for repeated subproblems.
n = 4: each row is one outer-loop turn
O(2ⁿ)
inner loop: j = 1…4
·
for i = 1…n: for j = 1…n: do constant work
O(n²)
i = 1…4
O(n log n)
O(n)
O(log n)
5
n
O(1)
Each of 4 outer turns makes 4 inner steps: 4 × 4 = 16 operations. For general n, the n-by-n work grid has n² cells, so this pattern is O(n²).
1 Sequential phases: add the work
+
n²
O(n²) dominates
Example: scan once, then compare every pair → n + n² = O(n²).
2 Repeated halving: count the cuts
n candidates
n/2 remain
After k cuts: n / 2ᵏ ≈ 1 so k ≈ log₂ n → O(log n) (Binary search on sorted data.)
n/4
3 Divide and conquer: count levels × work
n/2
Merge sort: Θ(log n) levels, Θ(n) total work per level → Θ(n log n). For recursion, check subproblem count and work at each level; repeated subproblems can change the total.
For a running-time function T(n), the symbols compare growth as n becomes large; constants and small n do not decide the class.
1 Scan every item · O(n)
n = 6 items; each is inspected once
6
One constant-time visit per item: 6 here, n in general.
O(g): upper bound
T(n) ≤ c·g(n) for large enough n
Θ(g): tight bound
a·g(n) ≤ T(n) ≤ b·g(n) for large enough n
2 Compare every ordered pair · O(n²)
Example: if T(n)=3n+2, then T(n) is Θ(n), hence also O(n²) (true but loose).
n = 4: for each first item, check all 4 seconds
Keep two separate questions in every answer
4 choices for the first position × 4 for the second = 16 cells. In general, n choices × n choices = n². If pairs are unordered, the exact count may differ, but the growth is still Θ(n²).
RESOURCE: time or memory?
State both: e.g., worst-case time O(n), auxiliary space O(1). A class alone is incomplete unless n and the case are clear.
3 Enumerate every subset · O(2ⁿ)
Each item creates a binary choice: exclude it or include it.
start
T(n) = 3n + 2, compared with constant multiples of n
n = 3 gives 2 × 2 × 2 = 8 subsets; n items give 2ⁿ possibilities.
10
What does Big O describe as input size n grows?
Which class best describes scanning every item in an n-item array once?
A program does O(n) work, then O(n²) work. What is the combined growth class?
Both loops run from 1 to n, and each inner-loop step does constant work. What is the total growth?
A loop repeatedly halves its remaining candidates until one remains. What is its growth class?
Inner loop starts at i, so each row does fewer steps.
Let n = array length. Count comparisons; state case, resource, and extra space.
j →
Ω(g): lower bound
T(n) ≥ c·g(n) for large enough n
i
✓
for i = 1…n: for j = i…n: do constant work
One pass; it exits as soon as it finds the target. If no match occurs, it checks every element.
At n = 4: 4 + 3 + 2 + 1 = 10 visits. In general: n + (n−1) + … + 1 = n(n+1)/2.
BEST CASE
target first
T
•
1 check
CASE: best, average, worst?
WORST CASE
last / absent
n checks
Compare typical work at n and 2n. Bar lengths use a log₂ scale; they show growth factors, not exact runtime.
4n — upper bound O(n)
CLASS
WORK MULTIPLIER
×1
T(n) = 3n + 2
~×1.33 (n=8→16)
Cheatsheet habit: name n → count work → identify case → report time and space separately.
In a nested loop, the inner loop runs from i to n for each outer i = 1…n. What is the asymptotic growth?
For a linear search that stops on the first match, what is the best-case time when the target is first?
If T(n) = 3n + 2, which statement gives its tight asymptotic class?
A hash-table lookup is usually expected O(1), but what can its worst-case time be?
Merge sort does Θ(n) total work at each of Θ(log n) levels. What is its total growth?
2n — lower bound Ω(n)
×2
×3
×4
1 · Name n (input size)
2 · Count work as n grows
3 · State case & resource
4 · Report bound / class
×256 when n: 8→16
Scan example: n comparisons at most → worst-case time Θ(n). A few fixed variables → auxiliary space Θ(1). Time and space measure different resources.
If T(n) = 3n + 2, which is a valid but loose upper bound?
For n = 8 and then n = 16, how does O(n²) work typically change?
A scan uses Θ(n) time in the worst case and a fixed number of extra variables. Which report correctly separates the resources?
For T(n) = 3n + 2, which pair of bounds establishes its tight growth class?