Asymptotic Notations: Big-Oh (O), Big-Omega (Ω), and Big-Theta (Θ)
Let f be a non negative function. Then we can define the three most common asymptotic bounds as follows.
Big-Oh(O)
We say that f(n) is Big-Ο of g(n), written as f(n) = Ο(g(n)), iff there are positive constants c and n0 such that
0 ≤ f(n) ≤ c ⋅ g(n) for all n ≥ n0
If f(n) = Ο(g(n)), we say that g(n) is an upper bound
Example
Let us consider a given function:
f(n) = 4 ⋅ n3 + 10n2 + 5n + 8
g(n) = n3
Checking whether f(n) = Ο(g(n)) or not?
Solution:
For above condition to be true
0 ≤ f(n) ≤ c ⋅ g(n)
4n3 + 10n2 + 5n + 8 ≤ c ⋅ n3
when c = 5 and n ≥ 4
f(n) is always lesser than g(n)
Hence above statement is true.
Big-Omega (Ω)
We say that f(n) is Big-Omega of g(n), written as f(n) = Ω(g(n)), iff there are positive constants c and n0 such that
0 ≤ c ⋅ g(n) ≤ f(n) for all n ≥ n0
If f(n) = Ω(g(n)), we say that g(n) is a lower bound
Example
Let us consider a given function:
f (n) = 3n + 2
g(n) = n
Checking whether f(n) = Ω(g(n)) or not?
Solution:
For above condition to be true
0 ≤ c ⋅ g(n) ≤ f(n)
c ⋅ n ≤ 3n + 2
when c = 1 and n ≥ 1
g(n) is always lesser than f(n)
Hence above statement is true.
Big-Theta (Θ)
We say that f(n) is Big-Theta
Big-Theta of g(n), written as f(n) = Θ(g(n)), iff there are positive constants c1, c2 and n0 such that
0 ≤ c1 ⋅ g(n) ≤ f(n) ≤ c2 ⋅ g(n) for all n ≥ no
Equivalently, f(n) = Θ(g(n)) if and only if f(n) = Ο(g(n)) and f(n) = Ω(g(n)). If f(n) = Θ (g(n)), we say that g(n) is a tight bound on f(n).
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
