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.
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
Worked example
- Copying
nitems 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 it
- 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.