Asymptotic Notations Masterclass: Big-O, Big-Omega, Big-Theta & Time-Space Complexity Analysis
Author: Bhuban Subedi | Subject: Data Structures and Algorithms (CACS201) | Semester: Third Semester
In programming, writing code that produces the correct output is only half the battle. As software scales to handle millions of records, an inefficient algorithm can bring down servers and freeze user interfaces.
To scientifically evaluate and compare algorithm performance without relying on specific hardware speeds or compiler optimizations, computer scientists use Asymptotic Analysis.
In the Tribhuvan University (TU) BCA Third Semester DSA (CACS201) curriculum, Asymptotic Notations (Big-O, Big-$\Omega$, Big-$\Theta$) and code complexity analysis appear consistently as fundamental 5-mark and 10-mark examination questions.
In this guide, we will break down the exact mathematical definitions, analyze the growth of functions, calculate time complexity for nested loops, and solve standard TU board problems.
1. What Is Asymptotic Analysis?
Asymptotic analysis measures how the runtime or memory requirements of an algorithm scale as the input size $n$ tends toward infinity ($n \to \infty$).
Instead of measuring wall-clock time in seconds (which varies depending on whether you run code on an old laptop or a high-end server), we count the growth rate of primitive operations as a mathematical function $f(n)$.
2. The Three Primary Asymptotic Notations
+-------------------+-------------------+------------------------------------+-----------------------+
| Notation | Name | Mathematical Bound | Meaning |
+-------------------+-------------------+------------------------------------+-----------------------+
| **$O$ (Big-O)** | Asymptotic Upper | $f(n) \le c \cdot g(n)$ | **Worst-case** upper |
| | Bound | for all $n \ge n_0$ | limit on execution. |
+-------------------+-------------------+------------------------------------+-----------------------+
| **$\Omega$ (Omega)| Asymptotic Lower | $f(n) \ge c \cdot g(n)$ | **Best-case** lower |
| | Bound | for all $n \ge n_0$ | guarantee. |
+-------------------+-------------------+------------------------------------+-----------------------+
| **$\Theta$ (Theta)| Asymptotic Tight | $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ | **Tight bound** |
| | Bound | for all $n \ge n_0$ | (exact growth rate). |
+-------------------+-------------------+------------------------------------+-----------------------+
A. Big-O Notation ($O$): Upper Bound
Big-O represents the upper bound on the runtime of an algorithm. It guarantees that the algorithm will never take more time than $c \cdot g(n)$ for sufficiently large inputs.
$$\mathbf{Definition:}\ f(n) = O(g(n)) \iff \exists\ c > 0, n_0 > 0 \text{ such that } 0 \le f(n) \le c \cdot g(n),\ \forall n \ge n_0$$
Runtime T(n)
^
| c * g(n) [Upper Bound]
| /
| /
| / f(n) [Actual Algorithm]
| / /
| / /
| / /
+-----/--/------------------> Input Size (n)
n0
B. Big-Omega Notation ($\Omega$): Lower Bound
Big-Omega represents the lower bound on runtime. It guarantees that an algorithm will take at least this much time.
$$\mathbf{Definition:}\ f(n) = \Omega(g(n)) \iff \exists\ c > 0, n_0 > 0 \text{ such that } 0 \le c \cdot g(n) \le f(n),\ \forall n \ge n_0$$
C. Big-Theta Notation ($\Theta$): Tight Bound
When an algorithm’s upper bound and lower bound share the same growth order, we describe it using Big-Theta.
$$\mathbf{Definition:}\ f(n) = \Theta(g(n)) \iff \exists\ c_1, c_2 > 0, n_0 > 0 \text{ such that } c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n),\ \forall n \ge n_0$$
$$\mathbf{Theorem:}\ f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))$$
3. Hierarchy & Growth Rate of Common Complexities
From most efficient (fastest) to least efficient (slowest):
$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$
+-------------------+---------------------------+--------------------------------------+
| Complexity Class | Name | Real Algorithm Example |
+-------------------+---------------------------+--------------------------------------+
| $O(1)$ | Constant Time | Array indexing (`arr[i]`), Stack Push|
| $O(\log n)$ | Logarithmic Time | Binary Search in sorted array |
| $O(n)$ | Linear Time | Linear Search, Single Loop Traversal |
| $O(n \log n)$ | Linearithmic Time | Merge Sort, Heap Sort, Quick Sort |
| $O(n^2)$ | Quadratic Time | Bubble Sort, Selection Sort, 2 Loops |
| $O(2^n)$ | Exponential Time | Recursive Fibonacci, Towers of Hanoi |
| $O(n!)$ | Factorial Time | Traveling Salesperson (Brute Force) |
+-------------------+---------------------------+--------------------------------------+
4. Practical Loop Complexity Calculation (TU Exam Method)
Example 1: Single Loop
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i;
}
- Initialization: 1 operation.
- Loop executes $n$ times $\implies$ Complexity $= \mathbf{O(n)}$.
Example 2: Nested Dependent Loops
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
count++;
}
}
- When $i = 0$, inner loop runs $0$ times.
- When $i = 1$, inner loop runs $1$ time.
- When $i = n-1$, inner loop runs $n-1$ times.
- Total iterations $= 0 + 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2} = \frac{n^2 – n}{2}$.
- Dropping lower-order terms and constants $\implies$ Complexity $= \mathbf{O(n^2)}$.
Example 3: Logarithmic Loop (Multiplication/Division Step)
int p = 1;
for (int i = 1; i < n; i = i * 2) {
p = p + 2;
}
- In iteration $k$, value of $i = 2^k$.
- The loop terminates when $2^k \ge n \implies k = \log_2 n$.
- Total iterations $= \mathbf{O(\log n)}$.
5. Solved TU Board Exam Question
Board Question:
“Prove formally using the mathematical definition of Big-O that $f(n) = 3n^2 + 5n + 7$ is $O(n^2)$.” (TU BCA 5 Marks)
Proof:
We need to find positive constants $c$ and $n_0$ such that:
$$3n^2 + 5n + 7 \le c \cdot n^2 \quad \text{for all } n \ge n_0$$
For all $n \ge 1$:
– $5n \le 5n^2$
– $7 \le 7n^2$
Therefore:
$$3n^2 + 5n + 7 \le 3n^2 + 5n^2 + 7n^2 = 15n^2$$
Thus, by choosing:
– Constant $\mathbf{c = 15}$
– Threshold $\mathbf{n_0 = 1}$
We have satisfied $0 \le 3n^2 + 5n + 7 \le 15n^2$ for all $n \ge 1$.
$$\mathbf{\therefore 3n^2 + 5n + 7 = O(n^2)\quad [Proved]}$$
Summary & TU Exam Takeaways
- Big-O provides the guaranteed upper bound (worst-case).
- Big-$\Omega$ provides the lower bound (best-case).
- Big-$\Theta$ describes the exact asymptotic behavior when upper and lower bounds match.
- When calculating complexity, always ignore constant coefficients ($5n \to n$) and lower-order terms ($n^2 + 100n \to n^2$).
