Asymptotic Notation

CS F364 — Design & Analysis of Algorithms | Summer 2026

Big-Oh, Big-Theta, Big-Omega — comparing growth rates

← Practice

NoteProblem 1

Prove the following function is \Theta(n^4):

T(n) = 2n^4 - 20n^3 - 200n^2 + 500n + 5000

We need constants c_1, c_2 > 0 and n_0 such that c_1 n^4 \le T(n) \le c_2 n^4 for all n \ge n_0.

Upper bound (O(n^4)): For n \ge 1, \begin{aligned} T(n) &\le 2n^4 + 500n + 5000 \\ &\le 2n^4 + 500n^4 + 5000n^4 = 5502\, n^4. \end{aligned} Take c_2 = 5502, n_0 = 1.

Lower bound (\Omega(n^4)): For n \ge 200, 20n^3 \le 0.1 n^4,\quad 200n^2 \le 0.005 n^4,\quad 500n \le 0.0025 n^4,\quad 5000 \le 0.025 n^4. Hence T(n) \ge 2n^4 - 0.1n^4 - 0.005n^4 - 0.0025n^4 - 0.025n^4 = 1.8675\, n^4. Take c_1 = 1.8675, n_0 = 200.

Thus T(n) = \Theta(n^4).

NoteProblem 2

For each running time below, select the lowest Big-Oh complexity O(f(n)):

\text{(a)}\; 500n + 5n^{1.5} + 50n\log_{10} n

\text{(b)}\; n^2\log_2 n + n(\log_2 n)^2

\text{(c)}\; 3\log_8 n + \log_2\log_2\log_2 n

\text{(d)}\; n\log_3 n + n\log_2 n

\text{(e)}\; 2n + n^{0.5} + 0.5n^{1.25}

  1. O(n^{1.5}) — the n^{1.5} term dominates.

  2. O(n^2\log n) — n^2\log n dominates n(\log n)^2.

  3. O(\log n) — \log_8 n dominates the iterated log.

  4. O(n\log n) — both terms are \Theta(n\log n) (change of base is constant).

  5. O(n) — the 2n term dominates n^{0.5} and 0.5n^{1.25}.

NoteProblem 3

For each group, sort the functions in increasing order of O-complexity:

  1. f_1(n)=n^{0.999999}\log n, f_2(n)=10^7 n, f_3(n)=(1.000001)^n, f_4(n)=n^2

  2. f_1(n)=2^{2^{1000000}}, f_2(n)=2^{100000n}, f_3(n)=\binom{n}{2}, f_4(n)=n\sqrt{n}

  3. f_1(n)=n^{\sqrt{n}}, f_2(n)=2^n, f_3(n)=n^{10}2^{n/2}, f_4(n)=\sum_{i=1}^{n}(i+1)

i. f_1(n) \prec f_2(n) \prec f_4(n) \prec f_3(n)

n^{0.999999}\log n grows slower than n (since exponent <1), 10^7 n is linear, n^2 is quadratic, and (1.000001)^n is exponential — the fastest.

ii. f_1(n) \prec f_4(n) \prec f_3(n) \prec f_2(n)

f_1(n)=2^{2^{1000000}} is a constant (no n in the exponent). n\sqrt{n}=n^{1.5}, \binom{n}{2}=\Theta(n^2), and 2^{100000n}=\Theta(2^{cn}) is exponential in n.

iii. f_4(n) \prec f_1(n) \prec f_3(n) \prec f_2(n)

\sum_{i=1}^n (i+1) = \Theta(n^2). n^{\sqrt{n}} is larger than any polynomial but smaller than 2^n. n^{10}2^{n/2} = \Theta(2^{n/2}), which grows slower than 2^n by a square-root factor.

NoteProblem 4

Let f(n) and g(n) be asymptotically positive functions. Prove or disprove:

  1. o(g(n)) \cap \omega(g(n)) = \emptyset

  2. f(n) = O(g(n)) \implies 2^{f(n)} = O(2^{g(n)})

  3. f(n) + g(n) = \Theta(\min(f(n), g(n)))

  4. f(n) + g(n) = \Theta(\max(f(n), g(n)))

(i) TRUE. If h(n) \in o(g(n)), then \lim_{n\to\infty} h(n)/g(n) = 0. If h(n) \in \omega(g(n)), then \lim_{n\to\infty} h(n)/g(n) = \infty. No function can satisfy both simultaneously. Hence the intersection is empty.

(ii) FALSE. Counterexample: f(n) = 2n, g(n) = n. Clearly 2n = O(n), but 2^{2n} = 4^n is not O(2^n) since \lim_{n\to\infty} 4^n/2^n = \lim_{n\to\infty} 2^n = \infty.

(iii) FALSE. Counterexample: f(n)=n, g(n)=n^2. Then f(n)+g(n)=\Theta(n^2) but \min(f(n),g(n))=n, and \Theta(n^2) \neq \Theta(n).

(iv) TRUE. Since \max(f(n),g(n)) \le f(n)+g(n) \le 2\max(f(n),g(n)) for all n, we have c_1=1, c_2=2, n_0=1. Thus f(n)+g(n)=\Theta(\max(f(n),g(n))).