Asymptotic Notation

This chapter establishes the foundational principles of asymptotic notation, encompassing Big O, Big Omega, and Big Theta. These formalisms are indispensable for rigorously analyzing and expressing the efficiency of algorithms, a core competency frequently assessed in CMI examinations. A thorough understanding of these concepts is paramount for advanced studies in algorithm design and complexity theory.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Big O Notation | | 2 | Big Omega (Ω) and Big Theta (Θ) Notation |

---

We begin with Big O Notation.

Part 1: Big O Notation

We study asymptotic notation to analyze the efficiency of algorithms, focusing on their behavior as input size grows without bound. This allows us to compare algorithms independent of specific hardware or implementation details.

---

Core Concepts

1. Big O Notation ( $O$ )

We use Big O notation to describe an asymptotic upper bound for the growth rate of a function. A function $f(n)$ is $O(g(n))$ if $f(n)$ grows no faster than $g(n)$ up to a constant factor for sufficiently large $n$ .

📐 Big O Definition

f(n) = O(g(n)) \iff \exists c > 0, n_0 \ge 0 \text{ such that } 0 \le f(n) \le c \cdot g(n) \text{ for all } n \ge n_0

Where: *

f(n)

and

g(n)

are functions mapping natural numbers to non-negative real numbers. *

c

is a positive constant. *

n_0

is a non-negative integer. When to use: To state an upper bound on an algorithm's running time or space complexity.

Worked Example 1: Polynomial Comparison

Show that $f(n) = 3n^2 + 2n + 5$ is $O(n^2)$ .

Step 1: Identify $f(n)$ and $g(n)$ .

> $f(n) = 3n^2 + 2n + 5$
> $g(n) = n^2$

Step 2: Find constants $c$ and $n_0$ such that $3n^2 + 2n + 5 \le c \cdot n^2$ for $n \ge n_0$ .

> We can bound each term:
> $3n^2 \le 3n^2 \quad \text{for } n \ge 1$
> $2n \le 2n^2 \quad \text{for } n \ge 1$
> $5 \le 5n^2 \quad \text{for } n \ge 1$

Step 3: Sum the bounds to find a value for $c$ .

> $3n^2 + 2n + 5 \le 3n^2 + 2n^2 + 5n^2 = 10n^2$
> Thus, we can choose $c=10$ and $n_0=1$ .

Answer: $f(n) = 3n^2 + 2n + 5$ is $O(n^2)$ with $c=10$ and $n_0=1$ .

Worked Example 2: Exponential Comparison (PYQ pattern)

Determine if $3^n = O(2^n)$ and if $3^n = 2^{O(n)}$ .
(Note: $f(n)=2^{O(g(n))}$ if $\exists c, n_0$ such that $f(n) \le 2^{c \cdot g(n)}$ for $n \ge n_0$ ).

Step 1: Analyze $3^n = O(2^n)$ . We need to find $c, n_0$ such that $3^n \le c \cdot 2^n$ .

> Dividing by $2^n$ :
> $(3/2)^n \le c$
> As $n \to \infty$ , $(3/2)^n \to \infty$ . No constant $c$ can bound $(3/2)^n$ for all $n \ge n_0$ .
> Therefore, $3^n = O(2^n)$ is false.

Step 2: Analyze $3^n = 2^{O(n)}$ . We need to find $c, n_0$ such that $3^n \le 2^{c \cdot n}$ .

> We know $3 = 2^{\log_2 3}$ .
> So, $3^n = (2^{\log_2 3})^n = 2^{n \log_2 3}$ .
> We need to find $c$ such that $2^{n \log_2 3} \le 2^{c \cdot n}$ .
> This inequality holds if $n \log_2 3 \le c \cdot n$ .
> We can choose $c = \log_2 3$ . Since $\log_2 3 \approx 1.58$ is a positive constant, and $n_0=1$ , the condition holds.

Answer: $3^n = O(2^n)$ is false. $3^n = 2^{O(n)}$ is true.

Worked Example 3: Logarithmic Comparison

Show that $f(n) = \log(n^3)$ is $O(\log n)$ .

Step 1: Simplify $f(n)$ .

> Using logarithm properties:
> $\log(n^3) = 3 \log n$

Step 2: Find constants $c$ and $n_0$ such that $3 \log n \le c \cdot \log n$ for $n \ge n_0$ .

> We can directly choose $c=3$ .
> For $n \ge 1$ , $\log n$ is defined and positive (for $n>1$ ).
> So, $3 \log n \le 3 \log n$ holds for $n \ge 2$ (to ensure $\log n > 0$ ).

Answer: $f(n) = \log(n^3)$ is $O(\log n)$ with $c=3$ and $n_0=2$ .

:::question type="MSQ" question="Let $f(n) = 2n^3 + 5n \log n + 100$ and $g(n) = n^3$ . Which of the following statements are true?" options=[" $f(n) = O(g(n))$ "," $g(n) = O(f(n))$ "," $f(n) = O(n^2)$ "," $f(n) = O(n^4)$ "] answer=" $f(n) = O(g(n))$ , $g(n) = O(f(n))$ , $f(n) = O(n^4)$ " hint="Identify the dominant terms for $f(n)$ and $g(n)$ . Recall that $O$ denotes an upper bound." solution="
Step 1: Analyze $f(n) = O(g(n))$ .
The dominant term in $f(n)$ is $2n^3$ . The dominant term in $g(n)$ is $n^3$ .
Since $n^3$ is the highest power in $f(n)$ , $f(n)$ grows at the same rate as $n^3$ .
Thus, $2n^3 + 5n \log n + 100 \le c \cdot n^3$ . We can choose $c=3$ (for $n \ge \text{some } n_0$ ).
So, $f(n) = O(g(n))$ is true.

Step 2: Analyze $g(n) = O(f(n))$ .
This means $n^3 \le c \cdot (2n^3 + 5n \log n + 100)$ .
Since $f(n)$ grows as $n^3$ , $n^3$ is bounded by $f(n)$ . We can choose $c=1$ and $n_0=1$ .
So, $g(n) = O(f(n))$ is true.

Step 3: Analyze $f(n) = O(n^2)$ .
The dominant term in $f(n)$ is $n^3$ . The dominant term in $n^2$ is $n^2$ .
Since $n^3$ grows faster than $n^2$ , $f(n)$ cannot be bounded by $c \cdot n^2$ .
So, $f(n) = O(n^2)$ is false.

Step 4: Analyze $f(n) = O(n^4)$ .
The dominant term in $f(n)$ is $n^3$ . The dominant term in $n^4$ is $n^4$ .
Since $n^3$ grows slower than $n^4$ , $f(n)$ is bounded by $c \cdot n^4$ . We can choose $c=1$ for $n \ge 1$ .
So, $f(n) = O(n^4)$ is true.
"
:::

---

2. Little O Notation ( $o$ )

We use Little O notation to describe a strict asymptotic upper bound. A function $f(n)$ is $o(g(n))$ if $f(n)$ grows strictly slower than $g(n)$ for sufficiently large $n$ . This implies that the ratio $f(n)/g(n)$ approaches $0$ as $n$ approaches infinity.

📐 Little O Definition

f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0

Where: *

f(n)

and

g(n)

are functions mapping natural numbers to non-negative real numbers, and

g(n) \ne 0

for sufficiently large

n

. When to use: To state that an algorithm is strictly better than a given upper bound. If

f(n) = o(g(n))

, then

f(n) = O(g(n))

is also true, but not vice-versa.

Worked Example:

Show that $f(n) = n^2$ is $o(n^3)$ .

Step 1: Set up the limit.

\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{n^2}{n^3}

Step 2: Evaluate the limit.

\lim_{n \to \infty} \frac{1}{n} = 0

Answer: Since the limit is $0$ , $n^2 = o(n^3)$ .

:::question type="MCQ" question="Which of the following statements is true?" options=[" $n \log n = o(n)$ "," $n = o(n)$ "," $n^2 = o(n^2 \log n)$ "," $2^n = o(n^k)$ for any constant $k$ "] answer=" $n^2 = o(n^2 \log n)$ " hint="Evaluate the limit $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ for each option. For $f(n) = o(g(n))$ , this limit must be 0." solution="
Step 1: Check $n \log n = o(n)$ .
>

\lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty

This is not 0, so

n \log n = o(n)

is false.

Step 2: Check $n = o(n)$ .
>

\lim_{n \to \infty} \frac{n}{n} = \lim_{n \to \infty} 1 = 1

This is not 0, so

n = o(n)

is false.

Step 3: Check $n^2 = o(n^2 \log n)$ .
>

\lim_{n \to \infty} \frac{n^2}{n^2 \log n} = \lim_{n \to \infty} \frac{1}{\log n} = 0

This is 0, so

n^2 = o(n^2 \log n)

is true.

Step 4: Check $2^n = o(n^k)$ for any constant $k$ .
> This means exponential functions grow slower than polynomial functions, which is false.
>

\lim_{n \to \infty} \frac{2^n}{n^k} = \infty \quad \text{(for any } k \text{ by L'Hôpital's rule)}

This is not 0, so

2^n = o(n^k)

is false.
"
:::

---

3. Big Omega Notation ( $\Omega$ )

We use Big Omega notation to describe an asymptotic lower bound. A function $f(n)$ is $\Omega(g(n))$ if $f(n)$ grows no slower than $g(n)$ up to a constant factor for sufficiently large $n$ .

📐 Big Omega Definition

f(n) = \Omega(g(n)) \iff \exists c > 0, n_0 \ge 0 \text{ such that } 0 \le c \cdot g(n) \le f(n) \text{ for all } n \ge n_0

Where: *

f(n)

and

g(n)

are functions mapping natural numbers to non-negative real numbers. *

c

is a positive constant. *

n_0

is a non-negative integer. When to use: To state a lower bound on an algorithm's running time or space complexity.

Worked Example:

Show that $f(n) = n^3 + 5n^2 + 10$ is $\Omega(n^3)$ .

Step 1: Identify $f(n)$ and $g(n)$ .

> $f(n) = n^3 + 5n^2 + 10$
> $g(n) = n^3$

Step 2: Find constants $c$ and $n_0$ such that $c \cdot n^3 \le n^3 + 5n^2 + 10$ for $n \ge n_0$ .

> We can choose $c=1$ .
> Then we need $n^3 \le n^3 + 5n^2 + 10$ .
> This inequality is clearly true for all $n \ge 0$ , as $5n^2 + 10$ is always non-negative.
> So, we can choose $c=1$ and $n_0=0$ .

Answer: $f(n) = n^3 + 5n^2 + 10$ is $\Omega(n^3)$ with $c=1$ and $n_0=0$ .

:::question type="MCQ" question="Which of the following is true for $f(n) = n^2 \log n + 100n$ ?" options=[" $f(n) = \Omega(n^3)$ "," $f(n) = \Omega(n \log n)$ "," $f(n) = \Omega(n^2 \log n)$ "," $f(n) = \Omega(n^2)$ "] answer=" $f(n) = \Omega(n \log n)$ , $f(n) = \Omega(n^2 \log n)$ , $f(n) = \Omega(n^2)$ " hint="For $f(n) = \Omega(g(n))$ , $f(n)$ must grow at least as fast as $g(n)$ . Consider the dominant term of $f(n)$ ." solution="
Step 1: Identify the dominant term of $f(n)$ .
The dominant term in $f(n) = n^2 \log n + 100n$ is $n^2 \log n$ .

Step 2: Check $f(n) = \Omega(n^3)$ .
Since $n^2 \log n$ grows slower than $n^3$ (e.g., $\lim_{n \to \infty} \frac{n^2 \log n}{n^3} = \lim_{n \to \infty} \frac{\log n}{n} = 0$ ), $f(n)$ cannot be lower bounded by $n^3$ .
So, $f(n) = \Omega(n^3)$ is false.

Step 3: Check $f(n) = \Omega(n \log n)$ .
Since $n^2 \log n$ grows faster than $n \log n$ , $f(n)$ is lower bounded by $n \log n$ .
We can choose $c=1$ and $n_0=1$ . $1 \cdot n \log n \le n^2 \log n + 100n$ for $n \ge 1$ .
So, $f(n) = \Omega(n \log n)$ is true.

Step 4: Check $f(n) = \Omega(n^2 \log n)$ .
Since $f(n)$ has $n^2 \log n$ as its dominant term, $f(n)$ grows at the same rate as $n^2 \log n$ .
We can choose $c=1$ and $n_0=1$ . $1 \cdot n^2 \log n \le n^2 \log n + 100n$ for $n \ge 1$ .
So, $f(n) = \Omega(n^2 \log n)$ is true.

Step 5: Check $f(n) = \Omega(n^2)$ .
Since $n^2 \log n$ grows faster than $n^2$ , $f(n)$ is lower bounded by $n^2$ .
We can choose $c=1$ and $n_0=1$ . $1 \cdot n^2 \le n^2 \log n + 100n$ for $n \ge 1$ .
So, $f(n) = \Omega(n^2)$ is true.
"
:::

---

4. Little Omega Notation ( $\omega$ )

We use Little Omega notation to describe a strict asymptotic lower bound. A function $f(n)$ is $\omega(g(n))$ if $f(n)$ grows strictly faster than $g(n)$ for sufficiently large $n$ . This implies that the ratio $f(n)/g(n)$ approaches $\infty$ as $n$ approaches infinity.

📐 Little Omega Definition

f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty

Where: *

f(n)

and

g(n)

are functions mapping natural numbers to non-negative real numbers, and

g(n) \ne 0

for sufficiently large

n

. When to use: To state that an algorithm is strictly worse than a given lower bound. If

f(n) = \omega(g(n))

, then

f(n) = \Omega(g(n))

is also true, but not vice-versa.

Worked Example:

Show that $f(n) = n^3$ is $\omega(n^2)$ .

Step 1: Set up the limit.

\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{n^3}{n^2}

Step 2: Evaluate the limit.

\lim_{n \to \infty} n = \infty

Answer: Since the limit is $\infty$ , $n^3 = \omega(n^2)$ .

:::question type="MCQ" question="Which of the following statements is true?" options=[" $\log n = \omega(n)$ "," $n \log n = \omega(n)$ "," $n^2 = \omega(n^2)$ "," $2^n = \omega(3^n)$ "] answer=" $n \log n = \omega(n)$ " hint="Evaluate the limit $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ . For $f(n) = \omega(g(n))$ , this limit must be $\infty$ ." solution="
Step 1: Check $\log n = \omega(n)$ .
>

\lim_{n \to \infty} \frac{\log n}{n} = 0 \quad \text{(by L'Hôpital's rule)}

This is not

\infty

, so

\log n = \omega(n)

is false.

Step 2: Check $n \log n = \omega(n)$ .
>

\lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty

This is

\infty

, so

n \log n = \omega(n)

is true.

Step 3: Check $n^2 = \omega(n^2)$ .
>

\lim_{n \to \infty} \frac{n^2}{n^2} = \lim_{n \to \infty} 1 = 1

This is not

\infty

, so

n^2 = \omega(n^2)

is false.

Step 4: Check $2^n = \omega(3^n)$ .
>

\lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} \left(\frac{2}{3}\right)^n = 0

This is not

\infty

, so

2^n = \omega(3^n)

is false.
"
:::

---

5. Big Theta Notation ( $\Theta$ )

We use Big Theta notation to describe an asymptotically tight bound. A function $f(n)$ is $\Theta(g(n))$ if $f(n)$ grows at the same rate as $g(n)$ up to constant factors for sufficiently large $n$ . This means $f(n)$ is both an upper bound and a lower bound for $g(n)$ .

📐 Big Theta Definition

f(n) = \Theta(g(n)) \iff \exists c_1, c_2 > 0, n_0 \ge 0 \text{ such that } 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \text{ for all } n \ge n_0

Alternatively, using limits (if the limit exists and is a positive constant):

f(n) = \Theta(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = L \text{ where } 0 < L < \infty<div class="math-display"><span class="katex-error" title="ParseError: KaTeX parse error: Can & #x27;t use function & #x27;

' in math mode at position 4731: …:**

Show that $̲ f(n) = 2n^2 + …" style="color:#cc0000">Where:
* <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math>f(n) and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">g(n)</annotation></semantics></math>g(n) are functions mapping natural numbers to non-negative real numbers.
* <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>c</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>c</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">c_1, c_2</annotation></semantics></math>c1,c2 are positive constants.
* <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>n</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">n_0</annotation></semantics></math>n0 is a non-negative integer.
* <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math>L is a positive finite constant.
When to use: To state that an algorithm's running time is precisely characterized by a given function, ignoring constant factors and lower-order terms.</div>
</div>

Worked Example:

Show that $f(n) = 2n^2 + 3n + 7$ is $\Theta(n^2)$ .

Step 1: Show $f(n) = O(n^2)$ .

> We need $2n^2 + 3n + 7 \le c_2 n^2$ .
> For $n \ge 1$ : $2n^2 + 3n + 7 \le 2n^2 + 3n^2 + 7n^2 = 12n^2$ .
> So, we can choose $c_2 = 12$ and $n_0 = 1$ .

Step 2: Show $f(n) = \Omega(n^2)$ .

> We need $c_1 n^2 \le 2n^2 + 3n + 7$ .
> For $n \ge 1$ : $c_1 n^2 \le 2n^2$ . We can choose $c_1 = 1$ .
> $1 \cdot n^2 \le 2n^2 + 3n + 7$ is true for $n \ge 0$ .
> So, we can choose $c_1 = 1$ and $n_0 = 1$ .

Answer: Since $f(n) = O(n^2)$ and $f(n) = \Omega(n^2)$ , $f(n) = \Theta(n^2)$ .
Alternatively, using limits:
>

\lim_{n \to \infty} \frac{2n^2 + 3n + 7}{n^2} = \lim_{n \to \infty} \left(2 + \frac{3}{n} + \frac{7}{n^2}\right) = 2

(a positive finite constant),

\lim_{n \to \infty} \frac{n^2 + 2n + 1}{n^2 + 2n + 1} = \lim_{n \to \infty} 1 = 1

f(n) = 3n^2 + \log n

\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{2n^2 + 5n}{n^2} = \lim_{n \to \infty} \left(2 + \frac{5}{n}\right) = 2

2

\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{\sqrt{n}}{\log n}

x = n

\lim_{x \to \infty} \frac{x^{1/2}}{\ln x} = \lim_{x \to \infty} \frac{\frac{1}{2}x^{-1/2}}{x^{-1}} = \lim_{x \to \infty} \frac{1}{2}x^{1/2} = \lim_{x \to \infty} \frac{\sqrt{x}}{2} = \infty

\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty

1 + 2 + \cdots + n = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}

\frac{n(n+1)}{2} = \frac{n^2 + n}{2}

\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1} 1

for each

\sum_{k=0}^{j-1} 1 = j

Step 4: Evaluate the middle sum.> $\sum_{j=0}^{i-1} j = \frac{(i-1)i}{2}

Step 5: Evaluate the outermost sum.
> $\sum_{i=0}^{n-1} \frac{(i-1)i}{2} = \frac{1}{2} \sum_{i=0}^{n-1} (i^2 - i)<div class="math-display"> W…" style="color:#cc0000">> This sum is dominated by the $i^2$ term.
> We know $\sum_{i=0}^{N} i^2 = \frac{N(N+1)(2N+1)}{6}$ .
> For $N=n-1$ , this is $\frac{(n-1)n(2n-1)}{6}$ , which is $\Theta(n^3)$ .
> The term $\sum i$ is $\Theta(n^2)$ .
> So the total sum is $\frac{1}{2} (\Theta(n^3) - \Theta(n^2)) = \Theta(n^3)$ .

Step 6: State the Big O complexity.
The dominant term is $n^3$ . The complexity is $O(n^3)$ .
The requested output is the exponent of $n$ .

Answer: 3
"
:::

---

Problem-Solving Strategies

<div class="callout-box my-4 p-4 rounded-lg border bg-green-500/10 border-green-500/30">
<div class="flex items-center gap-2 font-semibold mb-2">
💡
Using Limits for Asymptotic Comparison
</div>
<div class="prose prose-sm max-w-none">To quickly compare <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math>f(n) and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">g(n)</annotation></semantics></math>g(n), evaluate <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mrow><mi>lim</mi><mo>⁡</mo></mrow><mrow><mi>n</mi><mo>→</mo><mi mathvariant="normal">∞</mi></mrow></msub><mfrac><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><mrow><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></mfrac></mrow><annotation encoding="application/x-tex">\lim_{n \to \infty} \frac{f(n)}{g(n)}</annotation></semantics></math>limn→∞g(n)f(n): If limit is <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0: <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi>o</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = o(g(n))</annotation></semantics></math>f(n)=o(g(n)) and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi>O</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = O(g(n))</annotation></semantics></math>f(n)=O(g(n)). If limit is a positive finite constant <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math>L: <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = \Theta(g(n))</annotation></semantics></math>f(n)=Θ(g(n)), <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi>O</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = O(g(n))</annotation></semantics></math>f(n)=O(g(n)), and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">Ω</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = \Omega(g(n))</annotation></semantics></math>f(n)=Ω(g(n)). * If limit is <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∞</mi></mrow><annotation encoding="application/x-tex">\infty</annotation></semantics></math>∞: <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi>ω</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = \omega(g(n))</annotation></semantics></math>f(n)=ω(g(n)) and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">Ω</mi><mo stretchy="false">(</mo><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = \Omega(g(n))</annotation></semantics></math>f(n)=Ω(g(n)). This method is generally faster than finding specific constants <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>n</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">n_0</annotation></semantics></math>n0.</div>
</div>

<div class="callout-box my-4 p-4 rounded-lg border bg-green-500/10 border-green-500/30">
<div class="flex items-center gap-2 font-semibold mb-2">
💡
Identifying Dominant Terms
</div>
<div class="prose prose-sm max-w-none">When dealing with polynomial or mixed functions, always identify the term that grows fastest. This "dominant term" determines the asymptotic behavior. <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">n^k</annotation></semantics></math>nk grows faster than <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mi>j</mi></msup></mrow><annotation encoding="application/x-tex">n^j</annotation></semantics></math>nj if <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo> & gt;</mo><mi>j</mi></mrow><annotation encoding="application/x-tex">k & gt; j</annotation></semantics></math>k & gt;j. Exponential functions <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>b</mi><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">b^n</annotation></semantics></math>bn (for <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>b</mi><mo> & gt;</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">b & gt;1</annotation></semantics></math>b & gt;1) grow faster than any polynomial <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">n^k</annotation></semantics></math>nk. Polynomial functions <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">n^k</annotation></semantics></math>nk grow faster than any logarithmic function <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><msup><mo stretchy="false">)</mo><mi>j</mi></msup></mrow><annotation encoding="application/x-tex">(\log n)^j</annotation></semantics></math>(logn)j. Factorial <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo stretchy="false">!</mo></mrow><annotation encoding="application/x-tex">n!</annotation></semantics></math>n! grows faster than exponential <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>b</mi><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">b^n</annotation></semantics></math>bn. <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>a</mi></msub><mi>n</mi></mrow><annotation encoding="application/x-tex">\log_a n</annotation></semantics></math>logan and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>b</mi></msub><mi>n</mi></mrow><annotation encoding="application/x-tex">\log_b n</annotation></semantics></math>logbn are <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(\log n)</annotation></semantics></math>Θ(logn) (base doesn't matter for asymptotic growth). <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mi>c</mi></msup><mi>log</mi><mo>⁡</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">n^c \log n</annotation></semantics></math>nclogn grows slower than <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mrow><mi>c</mi><mo>+</mo><mi>ϵ</mi></mrow></msup></mrow><annotation encoding="application/x-tex">n^{c+\epsilon}</annotation></semantics></math>nc+ϵ for any <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>ϵ</mi><mo> & gt;</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">\epsilon & gt; 0</annotation></semantics></math>ϵ & gt;0.</div>
</div>

---

Common Mistakes

<div class="callout-box my-4 p-4 rounded-lg border bg-yellow-500/10 border-yellow-500/30">
<div class="flex items-center gap-2 font-semibold mb-2">
⚠️
Confusing $O$ and $\Theta$ 
</div>
<div class="prose prose-sm max-w-none">❌ Students often use <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi></mrow><annotation encoding="application/x-tex">O</annotation></semantics></math>O notation when they mean <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi></mrow><annotation encoding="application/x-tex">\Theta</annotation></semantics></math>Θ. <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi></mrow><annotation encoding="application/x-tex">O</annotation></semantics></math>O provides an upper bound, while <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi></mrow><annotation encoding="application/x-tex">\Theta</annotation></semantics></math>Θ provides a tight bound. If an algorithm takes <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n)</annotation></semantics></math>Θ(n) time, it also takes <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2) time, but saying it takes <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2) time is a weaker and less precise statement. ✅ Always strive for the tightest possible bound, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi></mrow><annotation encoding="application/x-tex">\Theta</annotation></semantics></math>Θ, unless specifically asked for an upper (<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi></mrow><annotation encoding="application/x-tex">O</annotation></semantics></math>O) or lower (<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Ω</mi></mrow><annotation encoding="application/x-tex">\Omega</annotation></semantics></math>Ω) bound. For example, merge sort is <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \log n)</annotation></semantics></math>O(nlogn) in all cases, but more precisely it is <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n \log n)</annotation></semantics></math>Θ(nlogn) in worst, average, and best cases.</div>
</div>

<div class="callout-box my-4 p-4 rounded-lg border bg-yellow-500/10 border-yellow-500/30">
<div class="flex items-center gap-2 font-semibold mb-2">
⚠️
Misinterpreting Logarithm Bases
</div>
<div class="prose prose-sm max-w-none">❌ Assuming <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mn>2</mn></msub><mi>n</mi></mrow><annotation encoding="application/x-tex">\log_2 n</annotation></semantics></math>log2n and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>ln</mi><mo>⁡</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">\ln n</annotation></semantics></math>lnn have different asymptotic growth rates. ✅ <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>a</mi></msub><mi>n</mi><mo>=</mo><mfrac><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>b</mi></msub><mi>n</mi></mrow><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>b</mi></msub><mi>a</mi></mrow></mfrac></mrow><annotation encoding="application/x-tex">\log_a n = \frac{\log_b n}{\log_b a}</annotation></semantics></math>logan=logbalogbn. Since <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mn>1</mn><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>b</mi></msub><mi>a</mi></mrow></mfrac></mrow><annotation encoding="application/x-tex">\frac{1}{\log_b a}</annotation></semantics></math>logba1 is a constant, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>a</mi></msub><mi>n</mi><mo>=</mo><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mi>b</mi></msub><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\log_a n = \Theta(\log_b n)</annotation></semantics></math>logan=Θ(logbn) for any bases <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo> & gt;</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">a, b & gt; 1</annotation></semantics></math>a,b & gt;1. The base of the logarithm does not affect its asymptotic complexity.</div>
</div>

---

Practice Questions

:::question type="MCQ" question="Which of the following statements is false?" options=[" $n^2 + 100n = O(n^2)$ "," $n \log n = \Omega(n)$ "," $2^{n+1} = O(2^n)$ "," $n! = O(n^n)$ "] answer=" $2^{n+1} = O(2^n)$ " hint="Carefully apply the definitions. For $O$ , check if $f(n) \le c \cdot g(n)$ . For $\Omega$ , check if $c \cdot g(n) \le f(n)$ ." solution="
Step 1: Check $n^2 + 100n = O(n^2)$ .
> We need to find $c, n_0$ such that $n^2 + 100n \le c \cdot n^2$ .
> For $n \ge 1$ , $n^2 + 100n \le n^2 + 100n^2 = 101n^2$ .
> So, $c=101, n_0=1$ . This statement is true.

Step 2: Check $n \log n = \Omega(n)$ .
> We need to find $c, n_0$ such that $c \cdot n \le n \log n$ .
> Divide by $n$ : $c \le \log n$ .
> We can choose $c=1$ . Then $1 \le \log n$ for $n \ge 2$ .
> So, $c=1, n_0=2$ . This statement is true.

Step 3: Check $2^{n+1} = O(2^n)$ .
> We need to find $c, n_0$ such that $2^{n+1} \le c \cdot 2^n$ .
> We know $2^{n+1} = 2 \cdot 2^n$ .
> So, $2 \cdot 2^n \le c \cdot 2^n$ . We can choose $c=2$ .
> This holds for all $n \ge 0$ . So, $c=2, n_0=0$ . This statement is true.

Step 4: Check $n! = O(n^n)$ .
> We need to find $c, n_0$ such that $n! \le c \cdot n^n$ .
> $n! = n \cdot (n-1) \cdot \ldots \cdot 1$ .
> $n^n = n \cdot n \cdot \ldots \cdot n$ (n times).
> Clearly, $n \cdot (n-1) \cdot \ldots \cdot 1 \le n \cdot n \cdot \ldots \cdot n$ for $n \ge 1$ .
> We can choose $c=1, n_0=1$ . This statement is true.

There seems to be an issue. All options are true. Let me re-evaluate the question prompt for "false" vs "true". The question asks "Which of the following statements is false?".
If all are true, then there is no false statement.
Let's re-think $2^{n+1} = O(2^n)$ . Yes, $2 \cdot 2^n = O(2^n)$ . This is indeed true.

The options must be constructed such that one is false.
Let me change one of the options to make it false.
Let's change option 3 to $2^n = O(n^k)$ for some $k$ . That would be false.
Or change option 4 to $n^n = O(n!)$ . That would be false.

Let's assume the question should have a false option. I'll make one of the options false.
Original question: " $2^{n+1} = O(2^n)$ "
My answer was "True".
Let's change option 3 to: " $2^n = O(n^3)$ "

Re-evaluating with modified options:
:::question type="MCQ" question="Which of the following statements is false?" options=[" $n^2 + 100n = O(n^2)$ "," $n \log n = \Omega(n)$ "," $2^n = O(n^3)$ "," $n! = O(n^n)$ "] answer=" $2^n = O(n^3)$ " hint="Carefully apply the definitions. For $O$ , check if $f(n) \le c \cdot g(n)$ . For $\Omega$ , check if $c \cdot g(n) \le f(n)$ ." solution="
Step 1: Check $n^2 + 100n = O(n^2)$ .
> We need to find $c, n_0$ such that $n^2 + 100n \le c \cdot n^2$ .
> For $n \ge 1$ , $n^2 + 100n \le n^2 + 100n^2 = 101n^2$ .
> So, $c=101, n_0=1$ . This statement is true.

Step 3: Check $2^n = O(n^3)$ .
> We need to find $c, n_0$ such that $2^n \le c \cdot n^3$ .
> Consider the limit $\lim_{n \to \infty} \frac{2^n}{n^3}$ . This limit is $\infty$ (exponential functions grow faster than polynomial functions).
> Therefore, no constant $c$ can bound $2^n$ by $c \cdot n^3$ for sufficiently large $n$ . This statement is false.

:::question type="NAT" question="Consider an algorithm with a running time $T(n) = 5n^3 - 2n^2 + 7$ . What is the smallest integer $k$ such that $T(n) = O(n^k)$ ?" answer="3" hint="Identify the dominant term in the polynomial." solution="
Step 1: Identify the dominant term of $T(n)$ .
The highest power of $n$ in $T(n) = 5n^3 - 2n^2 + 7$ is $n^3$ .

Step 2: Determine the Big O notation.
Since $n^3$ is the dominant term, $T(n) = O(n^3)$ .

Step 3: Find the smallest $k$ .
For $T(n) = O(n^k)$ to be true, $k$ must be at least the power of the dominant term. The smallest such integer $k$ is $3$ .
"
:::

:::question type="MSQ" question="Which of the following statements are true regarding the functions $f(n) = n^{\log n}$ and $g(n) = (\log n)^n$ ?" options=[" $f(n) = O(g(n))$ "," $f(n) = \Omega(g(n))$ "," $g(n) = O(f(n))$ "," $f(n) = \Theta(g(n))$ "] answer=" $f(n) = O(g(n))$ , $g(n) = \Omega(f(n))$ " hint="Take logarithms of both functions to simplify comparison. Recall that $a^b = e^{b \ln a}$ ." solution="
Step 1: Rewrite $f(n)$ and $g(n)$ using the exponential form $e^{\ln(\cdot)}$ .
$f(n) = n^{\log n} = e^{\ln(n^{\log n})} = e^{\log n \cdot \ln n}$ . (Assuming $\log n$ is natural log, $\ln n$ ).
Let's assume $\log n$ is base $e$ for consistency, so $\log n = \ln n$ .
$f(n) = e^{(\ln n)^2}$ .

$g(n) = (\log n)^n = e^{\ln((\ln n)^n)} = e^{n \ln(\ln n)}$ .

Step 2: Compare the exponents.
We need to compare $(\ln n)^2$ with $n \ln(\ln n)$ .
Let's consider the ratio of the exponents:
>

\lim_{n \to \infty} \frac{(\ln n)^2}{n \ln(\ln n)}

, while the denominator grows polynomially with respect to

1 + \frac{3}{n} \geq c

c

f(n) = (n+5)^2 = n^2 + 2 \cdot n \cdot 5 + 5^2 = n^2 + 10n + 25

g(n) = n^2 + 10n + 25

1 \cdot g(n) \leq f(n) \leq 1 \cdot g(n)$$
Since

f(n) = g(n)

, this becomes

1 \cdot g(n) \leq g(n) \leq 1 \cdot g(n)

, which is true.
Thus,

f(n) = \Theta(g(n))

.
If

f(n) = \Theta(g(n))

, it also implies

f(n) = \Omega(g(n))

and

f(n) = O(g(n))

. However,

\Theta(g(n))

is the most precise and comprehensive description of the relationship.

Let's check the options:
* $f(n) = \Omega(g(n))$ only: Incorrect, as $\Theta(g(n))$ is a tighter bound.
* $f(n) = O(g(n))$ only: Incorrect, as $\Theta(g(n))$ is a tighter bound.
* $f(n) = \Theta(g(n))$ : Correct, as $f(n)$ and $g(n)$ are identical.
* Neither $f(n) = \Omega(g(n))$ nor $f(n) = O(g(n))$ : Incorrect.

The most accurate statement is $f(n) = \Theta(g(n))$ ."
:::

---

Summary

❗ Key Formulas & Takeaways

| Formula/Concept | Expression |

|---|----------------|------------| | 1 | Big Omega (

\Omega

) |

f(n) = \Omega(g(n))

\exists c, n_0 > 0

s.t.

f(n) \geq c \cdot g(n)

for

n \geq n_0

. (Asymptotic Lower Bound) | | 2 | Big Theta (

\Theta

) |

f(n) = \Theta(g(n))

\exists c_1, c_2, n_0 > 0

s.t.

c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)

for

n \geq n_0

. (Asymptotically Tight Bound) | | 3 | Relationship |

f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))

| | 4 | Polynomial Dominance | For polynomials, the highest degree term determines the

\Theta

bound. | | 5 | Growth Order |

\log n < n < n \log n < n^2 < 2^n < n!

---

What's Next?

💡 Continue Learning

This topic connects to:

Big O ( $O$ ) Notation: Understanding upper bounds completes the set of primary asymptotic notations used for algorithm analysis.

Little O ( $o$ ) and Little Omega ( $\omega$ ) Notation: These notations describe strict upper and lower bounds, respectively, where the ratio $f(n)/g(n)$ approaches zero or infinity.

Algorithm Analysis: Applying these notations to determine the time and space complexity of various algorithms (e.g., sorting, searching, graph algorithms).

---

Chapter Summary

❗ Asymptotic Notation — Key Points

Asymptotic notation describes the limiting behavior of a function's growth rate as its input tends to infinity, abstracting away constant factors and lower-order terms.
Big O Notation ( $O(g(n))$ ) provides an asymptotic upper bound, indicating that $f(n)$ grows no faster than $g(n)$ for sufficiently large $n$ . Formally, $f(n) \le c \cdot g(n)$ for $n \ge n_0$ .
Big Omega Notation ( $\Omega(g(n))$ ) provides an asymptotic lower bound, indicating that $f(n)$ grows at least as fast as $g(n)$ for sufficiently large $n$ . Formally, $f(n) \ge c \cdot g(n)$ for $n \ge n_0$ .
Big Theta Notation ( $\Theta(g(n))$ ) provides an asymptotic tight bound, meaning $f(n)$ grows at the same rate as $g(n)$ for sufficiently large $n$ . This implies $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$ .
Understanding these notations is crucial for analyzing algorithm efficiency, predicting performance scalability, and comparing different algorithmic approaches independently of specific hardware or implementation details.
Common complexity classes, ordered by increasing growth rate, include $\Theta(1)$ , $\Theta(\log n)$ , $\Theta(n)$ , $\Theta(n \log n)$ , $\Theta(n^k)$ (for $k > 1$ ), and $\Theta(2^n)$ .

---

Chapter Review Questions

:::question type="MCQ" question="Which of the following statements is true regarding the relationship between $f(n) = 3n^2 + 5n + 10$ and $g(n) = n^2$ ?" options=[" $f(n) \in O(g(n))$ but not $f(n) \in \Omega(g(n))$ ", " $f(n) \in \Omega(g(n))$ but not $f(n) \in O(g(n))$ ", " $f(n) \in \Theta(g(n))$ ", " $f(n)$ is neither in $O(g(n))$ nor $\Omega(g(n))$ "] answer=" $f(n) \in \Theta(g(n))$ " hint="Consider the highest order term of $f(n)$ ." solution="For $f(n) = 3n^2 + 5n + 10$ and $g(n) = n^2$ , we can find constants $c_1, c_2, n_0$ such that $c_1 \cdot n^2 \le 3n^2 + 5n + 10 \le c_2 \cdot n^2$ for $n \ge n_0$ . For example, for $n \ge 1$ , $3n^2 \le 3n^2 + 5n + 10$ . Also, for $n \ge 1$ , $3n^2 + 5n + 10 \le 3n^2 + 5n^2 + 10n^2 = 18n^2$ . Thus, $f(n) \in \Theta(n^2)$ ."
:::

:::question type="NAT" question="What is the tightest asymptotic upper bound (Big Theta) for the function $T(n) = 5n \log_2 n + 2n + 7$ ? Express your answer as $n^k \log^m n$ where $k$ and $m$ are integers, or $n^k$ or $\log^m n$ . (e.g., $n \log n$ , $n^2$ , $\log n$ )" answer="n log n" hint="Identify the term with the highest growth rate." solution="The dominant term in $T(n) = 5n \log_2 n + 2n + 7$ is $5n \log_2 n$ . Therefore, $T(n) \in \Theta(n \log n)$ ."
:::

:::question type="MCQ" question="If $f(n) \in O(g(n))$ and $g(n) \in O(h(n))$ , which of the following statements is always true?" options=[" $f(n) \in \Omega(h(n))$ ", " $h(n) \in O(f(n))$ ", " $f(n) \in O(h(n))$ ", " $f(n) \in \Theta(h(n))$ "] answer=" $f(n) \in O(h(n))$ " hint="This reflects the transitive property of Big O notation." solution="Given $f(n) \in O(g(n))$ , there exist constants $c_1, n_1$ such that $f(n) \le c_1 g(n)$ for all $n \ge n_1$ . Given $g(n) \in O(h(n))$ , there exist constants $c_2, n_2$ such that $g(n) \le c_2 h(n)$ for all $n \ge n_2$ . Combining these, $f(n) \le c_1 g(n) \le c_1 (c_2 h(n)) = (c_1 c_2) h(n)$ for all $n \ge \max(n_1, n_2)$ . Thus, $f(n) \in O(h(n))$ with constant $c = c_1 c_2$ and $n_0 = \max(n_1, n_2)$ ."
:::

:::question type="NAT" question="What is the tightest asymptotic upper bound (Big Theta) for the sum $S(n) = \sum_{i=1}^{n} i$ ?" answer="n^2" hint="Recall the formula for the sum of the first $n$ positive integers." solution="The sum of the first $n$ positive integers is given by the formula $S(n) = \frac{n(n+1)}{2} = \frac{n^2 + n}{2}$ . The dominant term in this expression is $\frac{n^2}{2}$ . Therefore, $S(n) \in \Theta(n^2)$ ."
:::

---

What's Next?

💡 Continue Your CMI Journey

Building upon your understanding of asymptotic notation, the next critical step is to apply these tools to analyze the efficiency of various algorithms and data structures. Chapters on Sorting Algorithms, Searching, and fundamental Data Structures (e.g., Trees, Graphs, Hash Tables) will extensively utilize Big O, Omega, and Theta to evaluate and compare performance characteristics in terms of time and space complexity.

Asymptotic Notation

Asymptotic Notation

Chapter Contents

| Topic |

Part 1: Big O Notation

Core Concepts

1. Big O Notation (OOO)

2. Little O Notation (ooo)

3. Big Omega Notation (Ω\OmegaΩ)

4. Little Omega Notation (ω\omegaω)

5. Big Theta Notation (Θ\ThetaΘ)

6. Properties of Asymptotic Notations

7. Relationship between Notations

Advanced Applications

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

What's Next?

Part 2: Big Omega (Ω) and Big Theta (Θ) Notation

Core Concepts

1. Big Omega (Ω\OmegaΩ) Notation

2. Big Theta (Θ\ThetaΘ) Notation

Advanced Applications

Problem-Solving Strategies

Common Mistakes

Practice Questions

Summary

| Formula/Concept | Expression |

What's Next?

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Algorithms and Data Structures

Dynamic Programming

Hierarchical Data Structures

Algorithm Basics and Analysis

Other Key Data Structures

More Resources

Study Notes

Short Notes

Test Series

Mock Tests

Previous Year Papers

Chapter-wise PYQs

Chapter Practice

Why Choose MastersUp?

AI-Powered Plans

15,000+ Questions

Smart Analytics

Bookmark & Revise

1. Big O Notation ( $O$ )

2. Little O Notation ( $o$ )

3. Big Omega Notation ( $\Omega$ )

4. Little Omega Notation ( $\omega$ )

5. Big Theta Notation ( $\Theta$ )

1. Big Omega ( $\Omega$ ) Notation

2. Big Theta ( $\Theta$ ) Notation