Self-checkedTier 1 11 min readalgo.asymptotic-notation

Asymptotic notation

The notations O, Omega, Theta, little-o and little-omega with their exact definitions, the limit test, the properties that make them usable, the hierarchy of growth rates from constants to factorials, logarithm and exponent facts, Stirling's approximation and the standard sums, with the usual mistakes.

Why it exists

How fast is an algorithm? Counting seconds depends on the machine, the language and the input; counting exact operations depends on tiny details of the code. What matters when the input grows is how the cost grows: does doubling $n$ double the work, quadruple it, or square it? Asymptotic notation keeps exactly that and throws away constant factors and lower-order terms, so that algorithms can be compared independently of the machine. It is the vocabulary of every later page.

Prerequisites

None. This is a starting point.

None. You should be comfortable with logarithms, powers and limits at school level.

Precise definitions

All functions are from the natural numbers to the non-negative reals (running times). The statements concern large $n$ .

Big-O (upper bound). $f(n) = O(g(n))$ if there are constants $c > 0$ and $n_0$ such that

$0 \le f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0 .$

Big-Omega (lower bound). $f(n) = \Omega(g(n))$ if there are $c > 0$ and $n_0$ with $f(n) \ge c \cdot g(n) \ge 0$ for all $n \ge n_0$ .

Big-Theta (tight bound). $f(n) = \Theta(g(n))$ if there are $c_1, c_2 > 0$ and $n_0$ with $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$ . Equivalently $f = O(g)$ and $f = \Omega(g)$ .

Little-o and little-omega (strict). $f(n) = o(g(n))$ if for every $c > 0$ there is $n_0$ with $f(n) < c \cdot g(n)$ for $n \ge n_0$ ( $f$ grows strictly slower than $g$ ). $f(n) = \omega(g(n))$ if for every $c > 0$ eventually $f(n) > c \cdot g(n)$ .

The limit test. If $L = \lim_{n \to \infty} f(n) / g(n)$ exists, then

$L$	meaning
$L = 0$	$f = o(g)$ (so also $f = O(g)$ , not $\Omega(g)$ )
$0 < L < \infty$	$f = \Theta(g)$
$L = \infty$	$f = \omega(g)$ (so also $\Omega(g)$ , not $O(g)$ )

When the limit does not exist, use the definitions. L'Hopital's rule is the usual tool for the limit.

Reading the notation. $O(g)$ stands for a set of functions; " $f(n) = O(g(n))$ " really means $f \in O(g)$ . $O$ states an upper bound, it does not say the bound is tight: $n = O(n^2)$ is true. In an equation such as $T(n) = 2T(n/2) + \Theta(n)$ the $\Theta(n)$ stands for some function in that set. Saying that the worst case time is $O(n^2)$ and saying that an algorithm is $O(n^2)$ is a statement about an upper bound on the function "worst-case time", and it is a separate question whether it is best case, worst case or average case.

Properties.

Reflexivity: $f = \Theta(f)$ . Transitivity: $O$ , $\Omega$ , $\Theta$ , $o$ , $\omega$ are each transitive.
Symmetry: $f = \Theta(g)$ iff $g = \Theta(f)$ . Transpose symmetry: $f = O(g)$ iff $g = \Omega(f)$ ; $f = o(g)$ iff $g = \omega(f)$ .
Sums: $f + g = \Theta(\max(f, g))$ . So $n^2 + n \log n + 5 = \Theta(n^2)$ .
Products: if $f_1 = O(g_1)$ and $f_2 = O(g_2)$ then $f_1 f_2 = O(g_1 g_2)$ ; constants do not matter: $c f = \Theta(f)$ for $c > 0$ .
Polynomials: a polynomial of degree $d$ with positive leading coefficient is $\Theta(n^d)$ , and $(n + a)^b = \Theta(n^b)$ for constants $a, b$ .
Not every pair is comparable: $n$ and $n^{1 + \sin n}$ are neither $O$ nor $\Omega$ of each other. For the functions in this course (built from powers, logarithms, exponentials, factorials) one is always asymptotically below, equal to, or above the other.

The hierarchy of growth rates (each is $o$ of the next):

$1 \ll \log\log n \ll \log n \ll \log^k n \ll n^{\varepsilon} \ll n \ll n \log n \ll n^2 \ll n^3 \ll \cdots \ll 2^n \ll 3^n \ll n! \ll n^n .$

Any positive power of $n$ beats any power of $\log n$ ; any exponential $c^n$ ( $c > 1$ ) beats any polynomial; $n!$ beats every $c^n$ and is beaten by $n^n$ . Between polynomial and exponential lie functions such as $n^{\log n} = 2^{(\log n)^2}$ (super-polynomial but $o(2^n)$ ).

Logarithm and exponent facts. The base of a logarithm does not matter asymptotically: $\log_a n = \log_b n / \log_b a = \Theta(\log_b n)$ . But the base of an exponential does: $2^n = o(3^n)$ , and $2^{2n} = 4^n \ne O(2^n)$ , while $2^{n+1} = 2 \cdot 2^n = \Theta(2^n)$ . $a^{\log_b n} = n^{\log_b a}$ (so $2^{\log_2 n} = n$ and $4^{\log_2 n} = n^2$ ); $\log(n^k) = k \log n = \Theta(\log n)$ ; $\log(n!) = \Theta(n \log n)$ .

Stirling's approximation: $n! = \sqrt{2\pi n}\,(n/e)^n (1 + O(1/n))$ , which gives $\log_2 n! = n \log_2 n - n \log_2 e + \tfrac12 \log_2 (2 \pi n) + o(1) = \Theta(n \log n)$ .

Standard sums (used constantly when counting loop iterations):

Sum	Order
$1 + 2 + \cdots + n = n(n+1)/2$	$\Theta(n^2)$
$1^2 + 2^2 + \cdots + n^2 = n(n+1)(2n+1)/6$	$\Theta(n^3)$
$\sum_{i=1}^{n} i^k$	$\Theta(n^{k+1})$ for a constant $k \ge 0$
$1 + 2 + 4 + \cdots + 2^n = 2^{n+1} - 1$	$\Theta(2^n)$ (a geometric series with ratio above 1 is dominated by its last term)
$1 + \tfrac12 + \tfrac14 + \cdots$	$\Theta(1)$ (ratio below 1: dominated by the first term)
$H_n = 1 + \tfrac12 + \cdots + \tfrac1n \approx \ln n + 0.5772$	$\Theta(\log n)$
$\sum_{i=1}^{n} \log i = \log n!$	$\Theta(n \log n)$

How it works

The table evaluates the standard functions for $n$ doubling from 1 to 64. The point of the notation is visible: for small $n$ the order means little (at $n = 4$ the functions $n^2$ and $2^n$ are equal and $n^3$ is larger), but once $n$ passes a few tens the exponential and the factorial leave every polynomial behind: $2^{64}$ has 20 digits, $64!$ has 90, and $64^3 = 262144$ .

Growth of the standard functions: start

Computed by a script, not typed

n	log2 n	n	n log2 n	n^2	n^3	2^n	n!
1
2
4
8
16
32
64

Step 0

Compare the standard growth rates by evaluating them for n doubling from 1 to 64. Watch which column overtakes which.

0 / 7

computed by script: the quantities are evaluated or measured, one row at a time. python3 scripts/gen-algo-traces.py

Practical consequence: if an algorithm takes $10^9$ simple operations per second, an input of size $n = 10^5$ is fine for $\Theta(n \log n)$ (about $2 \cdot 10^6$ operations) and for $\Theta(n^2)$ ( $10^{10}$ , about ten seconds), hopeless for $\Theta(n^3)$ and unthinkable for $\Theta(2^n)$ . GATE questions ask you to rank functions and to decide which bound is correct.

Worked examples

EX 1Prove a Theta bound with constants

Easy

Show $3n^2 + 5n + 7 = \Theta(n^2)$ . Lower bound: $3n^2 + 5n + 7 \ge 3n^2$ for all $n \ge 1$ , so $c_1 = 3$ . Upper bound: for $n \ge 1$ we have $5n \le 5n^2$ and $7 \le 7n^2$ , so $3n^2 + 5n + 7 \le 15 n^2$ , giving $c_2 = 15$ with $n_0 = 1$ . (The constant 15 is the smallest integer that works from $n = 1$ , since at $n = 1$ the value is exactly 15.) By the limit test, $\lim (3n^2 + 5n + 7)/n^2 = 3$ , a positive constant: $\Theta(n^2)$ .

EX 2Decide with the limit test

Easy

(a) $n \log n$ versus $n^2$ : $\lim n \log n / n^2 = \lim \log n / n = 0$ , so $n \log n = o(n^2)$ . (b) $100 n$ versus $n^2/100$ : the ratio tends to 0: $100 n = o(n^2/100)$ , however large the constant 100 looks; constants never change the order. (c) $\log_2 n$ versus $\log_{10} n$ : ratio $\log_2 10$ , a constant: $\Theta$ . (d) $\sqrt{n}$ versus $\log^2 n$ : $\sqrt n = \omega(\log^2 n)$ (every positive power of $n$ beats every power of $\log n$ ). (e) $n^{1.01}$ versus $n \log^5 n$ : $\omega$ . All were confirmed by symbolic limits.

EX 3Exponentials are subtle

Medium

$2^{n+1} = 2 \cdot 2^n = \Theta(2^n)$ , so $2^{n+1} = O(2^n)$ is true. But $2^{2n} = (2^n)^2 = 4^n$ and $4^n / 2^n = 2^n \to \infty$ : $2^{2n} = \omega(2^n)$ , so $2^{2n} = O(2^n)$ is false. In the same way $(n+3)^5 = \Theta(n^5)$ (a constant shift does not matter in a polynomial) and $2^n = o(3^n)$ . And $n^3 = o(2^n)$ , although $n^3 > 2^n$ for $2 \le n \le 9$ (at $n = 10$ the value $2^{10} = 1024$ first exceeds $10^3$ ): the notation says nothing about small $n$ .

EX 4Factorials and logarithms of factorials

Medium

$n!$ versus $2^n$ : $n! = \omega(2^n)$ , because from $n = 4$ on every new factor of $n!$ is at least 4 while every new factor of $2^n$ is 2, so the ratio at least doubles at each step. $n!$ versus $n^n$ : $n! = o(n^n)$ (the ratio is about $\sqrt{2 \pi n}\, e^{-n}$ ). $\log(n!) = \Theta(n \log n)$ : the upper bound is immediate ( $n! \le n^n$ , so $\log n! \le n \log n$ ); the lower bound comes from keeping the largest $n/2$ factors, each at least $n/2$ , giving $\log n! \ge (n/2) \log(n/2)$ . So $\log(n!) = \Theta(\log (n^n))$ although $n! = o(n^n)$ : the logarithm hides the difference. This fact explains the $\Omega(n \log n)$ lower bound for comparison sorting ( $n!$ outcomes need $\log_2 n!$ comparisons).

EX 5Rank these functions

GATE level

Arrange in increasing order of growth: $n!$ , $2^n$ , $n^{\log_2 n}$ , $(\log_2 n)^{\log_2 n}$ , $4^{\log_2 n}$ , $n \log_2 n$ , $2^{\log_2 n}$ , $\sqrt n$ . Simplify first: $2^{\log_2 n} = n$ and $4^{\log_2 n} = n^2$ ; $(\log n)^{\log n} = 2^{\log n \cdot \log\log n} = n^{\log\log n}$ , a super-polynomial function that grows slower than $n^{\log n} = 2^{(\log n)^2}$ . Then compare in the hierarchy:

$\sqrt n \;<\; n \;<\; n \log n \;<\; n^2 \;<\; (\log n)^{\log n} \;<\; n^{\log n} \;<\; 2^n \;<\; n!$

where each term is $o$ of the next (checked pairwise with symbolic limits). A trap here is to put $n^{\log n}$ above $2^n$ : $n^{\log n} = 2^{(\log n)^2}$ and $(\log n)^2 = o(n)$ , so it is below.

Cheat box

$O$ : $f \le c g$ eventually. $\Omega$ : $f \ge c g$ . $\Theta$ : both. $o$ , $\omega$ : strict (every $c$ ). Limit of $f/g$ : 0 gives $o$ , positive constant gives $\Theta$ , infinity gives $\omega$ .
Drop constants and lower-order terms: $f + g = \Theta(\max)$ . Polynomial of degree $d$ is $\Theta(n^d)$ .
Order: $1 < \log n < \sqrt n < n < n \log n < n^2 < n^3 < 2^n < 3^n < n! < n^n$ .
Log base does not matter; exponential base does: $2^{n+1} = \Theta(2^n)$ but $2^{2n} \ne O(2^n)$ .
$a^{\log_b n} = n^{\log_b a}$ ; $\log n! = \Theta(n \log n)$ ; $H_n = \Theta(\log n)$ .
$\sum_{i \le n} i = \Theta(n^2)$ , $\sum i^2 = \Theta(n^3)$ , geometric ratio above 1: last term dominates.
$O$ is an upper bound only: $n = O(n^2)$ is true.

Traps and GATE patterns

Connections

Builds on

No prerequisites.

Unlocks

Analysing loops, time and spacePrerequisite of Analysing loops, time and spaceuses Solving recurrences: substitution, tree and Master theoremPrerequisite of Solving recurrences: substitution, tree and Master theoremuses

Across subjects

Limitsusesplanned

Within this subject

Analysing loops, time and spaceimplemented-by Solving recurrences: substitution, tree and Master theoremuses

The notation is applied to loops and recursions in analysing loops, time and space and in solving recurrences, where the Master theorem compares $f(n)$ with $n^{\log_b a}$ by exactly the tests above. It underlies the comparison of every algorithm in the later pages (sorting, searching, graph algorithms). The limit test is the one of calculus (limits).

PYQs

12 previous year questions from your book. I re-solved each one myself (11 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · Set 2 · MCQ · 1 markQ3 · page 97 of the book

Consider the following functions, where n is a
positive integer.
n1/3 , logn , log(n!) , 2logn
Which one of the following options lists the
functions in increasing order of asymptotic growth
rate? Note: Assume the base of log to be 2.

(a)logn , n1/3 , 2logn , log(n!)
(b)n1/3 , logn , log(n!) , 2logn
(c)logn , n1/3 , log(n!) , 2logn
(d)2logn , n1/3 , logn , log(n!)

GATE 2023 · MSQ · 1 markQ7 · page 98 of the book

Let f and g be functions of natural numbers given
by f(n)=n and g(n)=n2. Which of the following
statements is/are TRUE?

(a)f ∈ O(g)
(b)f ∈ ω(g)
(c)f ∈ o(g)
(d)f ∈ θ(g)

GATE 2022 · MCQ · 1 markQ9 · page 98 of the book

Which one of the following statements is TRUE
for all positive functions f(n)?

(a)f(n2) = θ(f(n)2), when f(n) is a polynomial
(b)f(n2)=o(f(n)2)
(c)f(n2) = O(f(n)2), when f(n) is an exponential function
(d)f(n2)= Ω (f(n)2) which one of the following options is correct?
(a)T(n) = θ((log n) 5/2)
(b)T(n) = θ(n)
(c)T(n) = θ(nlog n)
(d)T(n) = θ(n 5/2) ALGORITHMS

GATE 2021 · Set 1 · MCQQ11 · page 98 of the book

Consider the following three functions.
f1 = 10n
f2 = n logn
f3 = n✓n
Which one of the following options arranges the
function in the increasing order of asymptotic
growth rate?

(a)f2, f1, f3
(b)f3, f2, f1
(c)f2, f3, f1
(d)f1, f2, f3

GATE 2017 · Set 1 · MCQ · 2 marksQ14 · page 99 of the book

Consider the following functions from positives
integers to real numbers 10, √n, n, log2n, 100/n. The
CORRECT arrangement of the above functions in
increasing order of asymptotic complexity is:

(a)log2n, 100/n, 10, √n, n
(b)100/n, 10, log2n, √n, n
(c)10, 100/n , √n, log2 n, n
(d)100/n, log2n, 10 , √n, n

year not read yetQ19 · page 99 of the book

Let f(n) = n and g(n) = n (1 +sin n)
, where n is a
positive integer. Which of the following statements
is/are correct?
T(n) = {
2,
if 0 < n ≤ 2
I. f(n) = O(g(n))
Then T(n) in terms of θ notation is

(a)θ(log logn)
(b)θ(log n)
(c)θ(√n)
(d)θ(n) II. f(n) = Ω(g(n))
(a)Only I
(b)Only II
(c)Both I and II
(d)Neither I nor II ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2015 · Set 3 · MCQQ21 · page 100 of the book

Consider the equality X =∑i=0
n i3
following choices for X:
I. Θ(n4)
II. Θ(n5)
III. O(n5)
IV. Ω(n3)

GATE 2011 · MCQQ26 · page 101 of the book

Which of the given options provides the
increasing order of asymptotic complexity of
functions f 1 , f 2 , f 3 and f 4 ?
f1(n)=2n , f2(n)=n3/2, f3(n)=nlog2n , f4(n)=nlog n

(a)f3, f2, f4, f1
(b)f3, f2, f1, f4
(c)f2, f3, f1, f4
(d)f2, f3, f4, f1

GATE 2008 · MCQQ28 · page 101 of the book

Consider the following functions:
f(n) = 2n
g(n) = n!
h(n) = nlogn
Which of the following statements about the
asymptotic behaviour of f(n), g(n), and h(n) is
true?

(a)f(n) = O(g(n)); g(n) = O(h(n))
(b)f(n) = Ω(g(n)); g(n) = O(h(n))
(c)g(n) = O(f(n)); h(n) = O(f(n))
(d)h(n) = O(f(n)); g(n) = Ω(f(n))

GATE 2008 · MCQQ30 · page 101 of the book

Arrange the following functions in increasing
asymptotic order:
a. n1/3
b. en
c. n7/4
d. nlog9n
e. 1.0000001n

(a)a, d, c, e, b
(b)d, a, c, e, b
(c)a, c, d, e, b
(d)a, c, d, b, e

GATE 2017 · Set 2 · MCQ · 2 marksQ5 · page 146 of the book

Match the algorithms with their time complexities:
Algorithm
Time
complexity
P Towers of Hanoi with
n disks
i
Θ(n2 )
Q Binary search given n
sorted numbers
ii
Θ(nlog n)
R Heap sort given n
numbers at the worst
case
iii
Θ(2n )
S
Addition of two n × n
matrices
iv
Θ(logn)
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

(a)P-(iii), Q-(iv), R-(i), S-(ii)
(b)P-(iv), Q-(iii), R-(i), S-(ii)
(c)P-(iii), Q-(iv), R-(ii), S-(i)
(d)P-(iv), Q-(iii), R-(ii), S-(i)

GATE 2010 · MCQQ10 · page 148 of the book

Two alternative packages A and B are available
for processing a database having 10k records.
Package A requires 0.0001n2 time units and
package B requires 10n log10 n time units to
process n records. What is the smallest value of
k for which package B will be preferred over A?

(a)12
(b)10
(c)6
(d)5

Self-check

Question 1

Is $2^{n+1} = O(2^n)$ ? Is $2^{2n} = O(2^n)$ ?

Show answer

Yes to the first ( $2^{n+1} = 2 \cdot 2^n$ ), no to the second ( $2^{2n} / 2^n = 2^n \to \infty$ ).

Question 2

Which is larger asymptotically, $n^{\log n}$ or $2^n$ ?

Show answer

$2^n$ . Since $n^{\log_2 n} = 2^{(\log_2 n)^2}$ and $(\log n)^2 = o(n)$ , we have $n^{\log n} = o(2^n)$ .

Question 3

Give the order of $\sum_{i=1}^{n} i \log i$ .

Show answer

$\Theta(n^2 \log n)$ : the sum is at most $n \cdot n \log n$ , and the largest $n/2$ terms are each at least $(n/2) \log(n/2)$ .

Question 4

If $f(n) = O(n^2)$ and $g(n) = O(n^3)$ , what can be said about $f(n) + g(n)$ and $f(n) \cdot g(n)$ ?

Show answer

$f + g = O(n^3)$ and $f \cdot g = O(n^5)$ .

Revision card

One-screen revision

$O$ (upper), $\Omega$ (lower), $\Theta$ (both), $o$ , $\omega$ (strict); limit of $f/g$ : $0$ , constant, $\infty$ .
Drop constants and lower-order terms; log base is irrelevant, exponential base is not.
$1 < \log n < n^{\varepsilon} < n < n \log n < n^2 < 2^n < n! < n^n$ .
$\log n! = \Theta(n \log n)$ , $H_n = \Theta(\log n)$ , $\sum i = \Theta(n^2)$ .

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd edition), Chapter 3 Growth of Functions (asymptotic notation, standard notations and common functions)
·Kleinberg and Tardos, Algorithm Design, Chapter 2 Basics of Algorithm Analysis (2.2 asymptotic order of growth)

Verification

Every relation between two functions on this page (22 of them, including the ordered list of the example) was decided by a symbolic limit of f(n) / g(n) computed by sympy, an independent method (scripts/enum-checks/algo_analysis.py). The explicit constants 3 and 15 of the first example were checked for every n from 1 to 4999 and shown to be the smallest integers that work from n = 1. Stirling's approximation, the harmonic sum and the standard sums were checked numerically. The table of growth values is computed exactly by script (scripts/gen-algo-traces.py). Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (loop counts, recurrences, merge and quicksort counts and averages, hash probes and load-factor formulas, DP tables, MST and shortest-path runs, Floyd matrices); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose); tables and animations are machine output and were read, not re-run; One wrong number was fixed: 64! has 90 digits, not 89 (also in the generator scripts/gen-algo-traces.py and the table-growth trace), and a runtime remark was made exact (about ten seconds). Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Analysing loops, time and space