Asymptotic Bounds, Order of Growth & Growth Hierarchy
“Formal definitions of O, Omega, Theta, o, omega, limit tests, Stirling's approximation, and dominance ranking.”
1.Formal Set-Theoretic Definitions of Asymptotic Notations
§ 1.1.In algorithmic analysis, asymptotic notations quantify the limiting behavior of execution time or memory footprint as input size n tends to infinity, abstracting away hardware-specific machine constants.
1. Big-O Notation (Asymptotic Upper Bound):
O(g(n)) = { f(n) : exists c > 0, n_0 > 0 text{ such that } 0 <= f(n) <= c * g(n), forall n >= n_0 }
2. Big-Omega Notation (Asymptotic Lower Bound):
Omega(g(n)) = { f(n) : exists c > 0, n_0 > 0 text{ such that } 0 <= c * g(n) <= f(n), forall n >= n_0 }
3. Big-Theta Notation (Asymptotically Tight Bound):
Theta(g(n)) = { f(n) : exists c_1 > 0, c_2 > 0, n_0 > 0 text{ such that } 0 <= c_1 g(n) <= f(n) <= c_2 g(n), forall n >= n_0 }
Theorem: f(n) = Theta(g(n)) if and only if f(n) = O(g(n)) and f(n) = Omega(g(n)).
4. Strict Bounds (Little-o and Little-omega):
o(g(n)) = { f(n) : forall c > 0, exists n_0 > 0 text{ such that } 0 <= f(n) < c * g(n), forall n >= n_0 }
omega(g(n)) = { f(n) : forall c > 0, exists n_0 > 0 text{ such that } 0 <= c * g(n) < f(n), forall n >= n_0 }
2.The Limit Quotient Criterion & Growth Hierarchy
§ 1.2.When comparing continuous differentiable functions, L'Hopital's rule on the limit ratio L = lim_{n -> inf} [f(n) / g(n)] resolves dominance instantly:
- If L = 0, then f(n) = o(g(n)) and f(n) = O(g(n)), but f(n) != Theta(g(n)).
- If 0 < L < inf, then f(n) = Theta(g(n)), f(n) = O(g(n)), and f(n) = Omega(g(n)).
- If L = inf, then f(n) = omega(g(n)) and f(n) = Omega(g(n)), but f(n) != O(g(n)).
- If L oscillates and does not exist (e.g. n^(1 + sin n) vs n), limit test is inconclusive; one must resort to definitions.
The Canonical Growth Hierarchy:
1 prec log(log n) prec log n prec sqrt(log n) prec (log n)^k prec n^epsilon prec sqrt(n) prec n prec n log n prec n^2 prec n^k prec 2^(sqrt(n)) prec 2^n prec 3^n prec n! prec n^n
3. Worked Problem: Asymptotic Ranking of Non-Trivial Functions
When comparing exponential forms, take the base-2 logarithm of each function to compare exponents, but remember that f(n) < g(n) does not always mean log f(n) < log g(n) with the same asymptotic separation unless differences are polynomial.
Problem: Arrange the following four functions in strictly increasing order of asymptotic growth rate:
f1(n) = 2^{2^{log_2(log_2 n)}}
f2(n) = n^{log_2 n}
f3(n) = (log_2 n)^n
f4(n) = 2^{sqrt{n}}
Step 1: Simplify f1(n):
Recall 2^{log_2 x} = x. Thus 2^{log_2(log_2 n)} = log_2 n.
Therefore, f1(n) = 2^{log_2 n} = n. So f1(n) = Theta(n).
Step 2: Express remaining functions in base-2 exponential form 2^{g(n)}:
f2(n) = n^{log_2 n} = (2^{log_2 n})^{log_2 n} = 2^{(log_2 n)^2}.
f3(n) = (log_2 n)^n = (2^{log_2(log_2 n)})^n = 2^{n log_2(log_2 n)}.
f4(n) = 2^{sqrt{n}} = 2^{n^{0.5}}.
Step 3: Compare exponents of f2(n), f4(n), and f3(n):
Exponent of f2: e2(n) = (log_2 n)^2.
Exponent of f4: e4(n) = n^{0.5} = sqrt{n}.
Exponent of f3: e3(n) = n log_2(log_2 n).
Comparing e2(n) vs e4(n): Any positive polynomial n^epsilon dominates polylogarithmic powers (log n)^k.
Here n^{0.5} asymptotically dominates (log_2 n)^2. Thus e2(n) = o(e4(n)), meaning 2^{(log_2 n)^2} = o(2^{sqrt{n}}).
Comparing e4(n) vs e3(n): n^{0.5} is strictly smaller than n log_2(log_2 n). Thus e4(n) = o(e3(n)).
Step 4: Establish complete order:
f1(n) = n = 2^{log_2 n}
Exponents in increasing order: log_2 n << (log_2 n)^2 << n^{0.5} << n log_2(log_2 n).
Final verified ranking: f1(n) < f2(n) < f4(n) < f3(n).
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Best visual explanations of algorithm design and complexity analysis.
Exam-focused with GATE PYQ numericals on every major algorithm.