Unit 1: Complexity & Asymptotic Notation
Asymptotic Notation & Growth of Functions
10 min read · 100% complete
Explanation
Asymptotic notation is a way to describe how slow or fast an algorithm gets as the input grows.
Big-O is the upper limit — 'it will not be worse than this'.
Key exam points
- O = upper, Omega = lower, Theta = tight
- Master theorem has three cases
- Amortised != average case
Previous year questions
State and explain the Master theorem with all three cases.
2024 · 8 marks
Arrange the given functions in increasing order of growth rate.
2022 · 5 marks
Practice quiz
Which notation gives a tight bound?
Binary search runs in: