Past exam question: 2072 Ashwin (Regular), Q12
Data Structure and Algorithms · 4 marks
Open in the Padhaiko appTopic: Introduction
QuestionDefine an Omega and Theta notation with suitable example.
Solution
Big-Omega (Ω) Notation: f(n)=Ω(g(n)) iff there exist c>0,n0≥0 such that 0≤c⋅g(n)≤f(n) for all n≥n0.
- Example: f(n)=2n2+3n≥2n2 for all n≥1 (c=2,n0=1) ⟹f(n)=Ω(n2).
Big-Theta (Θ) Notation: f(n)=Θ(g(n)) iff there exist c1,c2>0,n0≥0 such that 0≤c1⋅g(n)≤f(n)≤c2⋅g(n) for all n≥n0.
- Example: 2n2≤2n2+3n≤5n2 for all n≥1 (c1=2,c2=5,n0=1) ⟹f(n)=Θ(n2).
Answer: Ω(g(n)) is the asymptotic lower bound and Θ(g(n)) is the tight two-sided bound; for f(n)=2n2+3n, both Ω(n2) and Θ(n2) hold for n≥1.
All past exam questions for Data Structure and Algorithms