Algorithms / Asymptotic Scenarios
Least You Need to Know: Mixed Big-O Scenarios
Mixed runtime questions combine scans, sorts, hash-table operations, and nested loops. Write each phase separately, then simplify to the dominant term.
The least you need to know
- Sequential phases add, then simplify to the dominant term.
- A sort plus a scan is usually `Θ(n log n)`.
- Two separate linear passes are still linear overall.
- Triangular nested loops are still quadratic.
- Average-case and worst-case data-structure costs should not be mixed silently.
Key notation
A(n)+B(n)
sum of phases
dominant term
largest asymptotic contributor
average vs. worst case
state the performance model
Tiny worked example
- Copying `n` items is `Θ(n)`.
- Sorting them with merge sort is `Θ(n log n)`.
- A final scan is `Θ(n)`.
- The total is `Θ(n log n)`.
Common mistakes
- Students often multiply sequential phases that should be added.
- Students often let constants distract them from the dominant growth rate.
- Students often switch between average-case and worst-case without saying so.
How to recognize this kind of problem
- List each phase separately before combining them.
- Ask whether a loop is nested or merely repeated later.
- After summing, keep only the tight dominant growth rate.
Next recommended lesson
Continue through this topic with Least You Need to Know: Backtracking as Search Over Partial Choices.
Least You Need to Know: Backtracking as Search Over Partial ChoicesRelated lessons
Keep going with nearby lessons in the same topic.