Back to course home
0% completed
Vote For New Content
Comparing Asymptotic Notations
Overview of Asymptotic Notations
In algorithm analysis, asymptotic notations describe the growth rates of functions as input size becomes very large. Each notation serves a specific purpose in bounding or comparing functions:
- Big-O Notation (O) – Defines an upper bound.
- Big-Omega Notation (Ω) – Defines a lower bound.
- Big-Theta Notation (Θ) – Describes a tight (exact) bound, covering both upper and lower bounds.
- Little-o Notation (o) – Describes a function that grows strictly slower than another.
- Little-omega Notation (ω) – Describes a function that grows strictly faster than another.
Comparison Table of Asymptotic Notations
| Notation | Type of Bound | Defines | Description | Example Relationship |
|---|---|---|---|---|
| Big-O (O) | Upper Bound | Worst-case scenario | f(n) grows no faster than g(n) | f(n) = O(n^2) |
| Big-Omega (Ω) | Lower Bound | Best-case scenario | f(n) grows no slower than g(n) | f(n) = \Omega(n) |
| Big-Theta (Θ) | Tight Bound | Exact rate | f(n) grows at the same rate as g(n) | f(n) = \Theta(n \log n) |
| Little-o (o) | Strictly Upper | Strictly slower rate | f(n) grows strictly slower than g(n) | f(n) = o(n^2) for f(n) = n |
| Little-omega (ω) | Strictly Lower | Strictly faster rate | f(n) grows strictly faster than g(n) | f(n) = \omega(n) for f(n) = n^2 |
.....
.....
.....
Like the course? Get enrolled and start learning!
On this page
Overview of Asymptotic Notations
Comparison Table of Asymptotic Notations