Algorithm I - Hoang Anh Duc - MIM - HUS - VNU

Work 2.

• Show that:

$$\begin{aligned}[t] & (a) \space 7x \text{ is } O(x^3) \quad & (e) \space & \log(n!) \text{ is } O(n \log n) \quad \\[5pt] & (b) \space x^3 \text{ is not } O(x^2) \quad & (f) \space & n^3 \text{ is } O(2^n) \quad \\[5pt] & (c) \space 1 + 2 + \ldots + n \text{ is } O(n^2) \quad & (g) \space & \log n \text{ is } O(n) \quad \\[5pt] & (d) \space n! = 1 \times 2 \times \ldots \times n \text{ is } O(n^n) \quad & (h) \space & \forall b > 1, \forall k > 0 , \log_b(n^k) \text{ is } O(\log n) \quad \end{aligned}$$

Block

• Note: If not addressed then assume $\log(n) = \log_2(n)$

• (a) $\quad 7x \text{ is } O(x^3)$

$$\begin{align} & \text{To prove that } 7x \in O(x^3) \text{, we need to find} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall x > k \mid 7x \leq \mathit{C} \cdot x^3 \quad \\[5pt] & \text{When } x > 1, \text{ we have } 7x \leq 7x^3 \equiv x \leq x^3 \quad \\[5pt] & \text{Therefore, with } \mathit{C} = 7, k = 1 \text{ as our witnesses} \quad \\[5pt] & \text{We have shown that } 7x \in O(x^3) \quad \\[5pt] \end{align}$$

Block

• (b) $\quad x^3 \text{ is not } O(x^2)$

$$\begin{align} & \text{To prove that } x^3 \notin O(x^2) \text{, we need to show that} \quad \\[5pt] & \text{No constants }\mathit{C}, k \text{ satisfy } \forall x > k \mid x^3 \leq \mathit{C} \cdot x^2 \quad \\[5pt] & \text{Proof by contradiction:} \quad \\[5pt] & \text{Assume that such constants } \mathit{C}, k \text{ exists, then:} \quad \\[5pt] & \exists \space \mathit{C} \mid \forall x > k \text{ satisfy the statement:} \quad \\[5pt] & x^3 \leq \mathit{C} \cdot x^2 \equiv x \leq \mathit{C} \implies \text{ x is bounded by } \mathit{C} \quad \\[5pt] & \text{Which contradicts our assumption of } \forall x > k \quad \\[5pt] & \text{Therefore } x^3 \notin O(x^2) \quad \\[5pt] \end{align}$$

Block

• (c) $\quad 1 + 2 + \ldots + n \text{ is } O(n^2)$

$$\begin{align} & \text{To prove that } 1 + 2 + \ldots + n \in O(n^2) \text{, we need to find} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall n > k \mid 1 + 2 + \ldots + n \leq \mathit{C} \cdot n^2 \quad \\[7pt] & \text{Let } S(n) = 1 + 2 + \ldots + n = \frac{n(n+1)}{2} \implies \forall n > k \mid S(n) \leq \mathit{C} \cdot n^2 \quad \\[7pt] & S(n) = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} \leq \frac{n^2 + n^2}{2} = \frac{2n^2}{2} = n^2 \quad \\[7pt] & \text{So when } n > 1, \text{ we have } S(n) \leq n^2 \equiv \frac{n(n+1)}{2} \leq n^2 \quad \\[7pt] & \text{Therefore, with } \mathit{C} = 1, k = 1 \text{ as our witnesses} \quad \\[5pt] & \text{We have shown that } 1 + 2 + \ldots + n \in O(n^2) \quad \\[5pt] \end{align}$$

Block

• (d) $\quad n! = 1 \times 2 \times \ldots \times n \text{ is } O(n^n)$

$$\begin{align} & \text{To prove that } n! = 1 \times 2 \times \ldots \times n \in O(n^n) \text{, we need to find} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall n > k \mid n! \leq \mathit{C} \cdot n^n \quad \\[5pt] & \text{When } n > 1, \text{ we have } n! \leq n \times n \times \ldots \times n = n^n \quad \\[5pt] & \text{Therefore, with } \mathit{C} = 1, k = 1 \text{ as our witnesses} \quad \\[5pt] & \text{We have shown that } n! = 1 \times 2 \times \ldots \times n \in O(n^n) \quad \\[5pt] \end{align}$$

Block

• (e) $\quad \log(n!) \text{ is } O(n \log n)$

$$\begin{align} & \text{To prove that } \log(n!) \in O(n \log n) \text{, we need to find} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall n > k \mid \log(n!) \leq \mathit{C} \cdot n \log n \quad \\[5pt] & \text{We have: } \log(n!) = \log(1 \times 2 \times \ldots \times n) \quad \\[5pt] & \qquad \qquad \space \space n \log n = \log(n^n) = \log(n \times n \times \ldots \times n) \quad \\[5pt] & \text{Leveraging (d), when } n > 1, \text{ we have:} \quad \\[5pt] & n! \leq n^n \equiv \log(n!) \leq \log(n^n) \equiv \log(n!) \leq n \log n \quad \\[5pt] & \text{Therefore, with } \mathit{C} = 1, k = 1 \text{ as our witnesses} \quad \\[5pt] & \text{We have shown that } \log(n!) \in O(n \log n) \quad \\[5pt] \end{align}$$

Block

• (f) $\quad n^3 \text{ is } O(2^n)$

$$\begin{align} & \text{To prove that } n^3 \in O(2^n) \text{, we need to find} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall n > k \mid n^3 \leq \mathit{C} \cdot 2^n \quad \\[5pt] & \text{We evaluate the limits as n } \rightarrow \infty \quad \\[7pt] & \lim_{n \rightarrow \infty} \frac{n^3}{2^n} \stackrel{\small{\text{L'Hopital}}}{=} \lim_{n \rightarrow \infty} \frac{3n^2}{2^n \ln^2 2} \stackrel{\small{\text{L'Hopital}}}{=} \lim_{n \rightarrow \infty} \frac{6}{2^n \ln^3 2} = 0 \\[7pt] & \text{Since the limit approaches 0, this means} \quad \\[5pt] & \text{That } n^3 \text{ grows much slower} \quad \\[5pt] & \text{Than } 2^n \text{ as } n \rightarrow \infty \implies \exists \mathit{C}, \forall n > k \mid n^3 \leq \mathit{C} \cdot 2^n \quad \\[5pt] & \text{Therefore } n^3 \in O(2^n) \quad \\[5pt] \end{align}$$

Block

• (g) $\quad \log n \text{ is } O(n)$

$$\begin{align} & \text{To prove that } \log n \in O(n) \text{, we need to find} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall n > k \mid \log n \leq \mathit{C} \cdot n \quad \\[5pt] & \text{We evaluate the limits as n } \rightarrow \infty \quad \\[7pt] & \lim_{n \rightarrow \infty} \frac{\log n}{n} \stackrel{\small{\text{L'Hopital}}}{=} \lim_{n \rightarrow \infty} \frac{1}{n} = 0 \\[7pt] & \text{Since the limit approaches 0, this means} \quad \\[5pt] & \text{That } \log n \text{ grows much slower} \quad \\[5pt] & \text{Than } n \text{ as } n \rightarrow \infty \implies \exists \mathit{C}, \forall n > k \mid \log n \leq \mathit{C} \cdot n \quad \\[5pt] & \text{Therefore } \log n \in O(n) \quad \\[5pt] \end{align}$$

Block

• (h) $\quad \forall b > 1, \forall k > 0 , \log_b(n^k) \text{ is } O(\log n)$

$$\begin{align} & \text{To prove that } \log_b(n^k) \in O(\log n) \mid \forall b > 1, \forall k > 0 \quad \\[5pt] & \text{We need to find:} \quad \\[5pt] & \text{Constants }\mathit{C}, k \text{ such that } \forall n > k \mid \log_b(n^k) \leq \mathit{C} \cdot \log n \quad \\[5pt] & \text{We evaluate: } \quad \\[7pt] & \log_b(n^k) = k \cdot \log_b(n) = k \cdot \frac{\log(n)}{\log(b)} = \frac{k}{\log(b)} \cdot \log(n) \quad \\[7pt] & \text{Because } b > 1, k > 0, \frac{k}{\log(b)} \text{ is positive and finite} \quad \\[7pt] & \text{We can choose } \mathit{C} = \frac{k}{\log(b)} \text{ and } k = 1 \text{, such that} \quad \\[7pt] & \log_b(n^k) \leq \mathit{C} \cdot \log n \text{, we have our witnesses} \quad \\[5pt] & \text{Therefore } \log_b(n^k) \in O(\log n) \quad \\[5pt] \end{align}$$

Block

Work 3.

$$\begin{align} \text{Explains what it means for a function } \mathcal{f} : \mathbb{R} \rightarrow \mathbb{R} \text{ to be } O(1) \quad \\[5pt] \end{align}$$

Block

$$\begin{align} & \text{Let } \mathcal{f}(n) : \mathbb{R} \rightarrow \mathbb{R}, \mathcal{f}(n) \in O(1) \quad \\[5pt] & \text{This statement holds if and only if: } \quad \\[5pt] & \exists \mathit{C} \in \mathbb{R} \mid \mathit{C} > 0 \text{ and } \exists k \in \mathbb{N} \mid \forall n \geq k \text{, such that:} \quad \\[5pt] & | \mathcal{f}(n) | \leq \mathit{C} \cdot 1 \equiv | \mathcal{f}(n) | \leq \mathit{C} \quad \\[5pt] \end{align}$$

Block

Work 4.

• Show that:

$$\begin{align} & (a) \quad x^3 \text{ is } O(x^4) \text{ but is not } O(x^3) \quad \\[7pt] & (b) \quad 3x^4 + 1 \text{ is } O\left(\frac{x^4}{2}\right) \text{ and } \frac{x^4}{2} \text{ is } O(3x^4 + 1) \quad \\[7pt] & (c) \quad x \log x \text{ is } O(x^2) \text{ but } x^2 \text{ is not } O(x \log x) \quad \\[5pt] & (d) \quad 2^n \text{ is } O(3^n) \text{ but } 3^n \text{ is not } O(2^n) \quad \\[5pt] \end{align}$$

Block

• (a) $\quad x^3 \text{ is } O(x^4) \text{ but is not } O(x^3)$

$$\begin{align} & \text{We prove that } x^3 \in O(x^4) \text{ first} \quad \\[5pt] & \text{We need to find constants }\mathit{C}_1, k_1 \text{ such that } \quad \\[5pt] & \forall x > k_1 \mid x^3 \leq \mathit{C}_1 \cdot x^4 \quad \\[5pt] & \text{We evaluate the limits as } x \rightarrow \infty \quad \\[7pt] & \lim_{x \rightarrow \infty} \frac{n^3}{n^4} = \lim_{x \rightarrow \infty} \frac{1}{x} = 0 \\[7pt] & \text{Since the limit approaches 0, this means} \quad \\[5pt] & \text{That } x^3 \text{ grows much slower} \quad \\[5pt] & \text{Than } x^4 \text{ as } x \rightarrow \infty \implies \exists \mathit{C}_1, \forall x > k_1 \mid x^3 \leq \mathit{C}_1 \cdot x^4 \quad \\[5pt] & \text{Therefore } x^3 \in O(x^4) \quad \\[5pt] \end{align}$$

Block

$$\begin{align} & \text{Next, we prove that } x^3 \notin O(x^3) \quad \\[5pt] & \text{We need to show that no constants }\mathit{C}_2, k_2 \text{ satisfy } \quad \\[5pt] & \forall x > k_2 \mid x^3 \leq \mathit{C}_2 \cdot x^3 \quad \\[5pt] & \text{Proof by contradiction:} \quad \\[5pt] & \text{Assume that such constants } \mathit{C}_2, k_2 \text{ exists, then:} \quad \\[5pt] & \exists \space \mathit{C}_2 \mid \forall x > k_2 \text{ satisfy the statement:} \quad \\[5pt] & x^3 \leq \mathit{C}_2 \cdot x^3 \equiv 1 \leq \mathit{C}_2 \implies x \text{ is bounded by itself} \quad \\[5pt] & \text{Which contradicts our assumption of } \forall x > k_2 \quad \\[5pt] & \text{Therefore } x^3 \notin O(x^3) \quad \\[5pt] \end{align}$$

Block

• (b) $\quad 3x^4 + 1 \text{ is } O\left(\frac{x^4}{2}\right) \text{ and } \frac{x^4}{2} \text{ is } O(3x^4 + 1)$

$$\begin{align} & \text{We prove that } 3x^4 + 1 \in O\left(\frac{x^4}{2}\right) \text{ first} \quad \\[7pt] & \text{We need to find constants }\mathit{C}_1, k_1 \text{ such that } \quad \\[7pt] & \forall x > k_1 \mid 3x^4 + 1 \leq \mathit{C}_1 \cdot \frac{x^4}{2} \quad \\[7pt] & \text{When } x > 1, \text{ we have } 3x^4 + 1 \leq \mathit{C}_1 \cdot \frac{x^4}{2} \equiv 3 + \frac{1}{x^4} \leq \frac{\mathit{C}_1}{2} \quad \\[7pt] & \text{As } x \rightarrow \infty , \text{ the inequality becomes } 3 \leq \frac{\mathit{C}_1}{2} \equiv \mathit{C}_1 \geq 6 \quad \\[7pt] & \text{Therefore, with } \mathit{C}_1 = 6, k_1 = 1 \text{ as our witnesses} \quad \\[5pt] & \text{We have shown that } 3x^4 + 1 \in O\left(\frac{x^4}{2}\right) \quad \\[5pt] \end{align}$$

Block

$$\begin{align} & \text{Next, we prove that } \frac{x^4}{2} \in O(3x^4 + 1)\quad \\[7pt] & \text{We need to find constants }\mathit{C}_2, k_2 \text{ such that } \quad \\[7pt] & \forall x > k_2 \mid \frac{x^4}{2} \leq \mathit{C}_2 \cdot (3x^4 + 1) \quad \\[7pt] & \text{When } x > 1, \text{ we have:} \quad \\[7pt] & \frac{x^4}{2} \leq \mathit{C}_2 \cdot (3x^4 + 1) \equiv \frac{1}{2} \leq \mathit{C}_2 \cdot \left(3 + \frac{1}{x^4} \right) \quad \\[7pt] & \text{As } x \rightarrow \infty , \text{ the inequality becomes } \frac{1}{2} \leq 3\mathit{C}_2 \equiv \mathit{C}_2 \geq \frac{1}{6} \quad \\[7pt] & \text{Therefore, with } \mathit{C}_2 = \frac{1}{6}, k_2 = 1 \text{ as our witnesses} \quad \\[7pt] & \text{We have shown that } \frac{x^4}{2} \in O(3x^4 + 1) \quad \\[5pt] \end{align}$$

Block

• (c) $\quad x \log x \text{ is } O(x^2) \text{ but } x^2 \text{ is not } O(x \log x)$

$$\begin{align} & \text{We evaluate both statements when } x \rightarrow \infty \quad \\[5pt] \end{align}$$

Block

• (d) $\quad 2^n \text{ is } O(3^n) \text{ but } 3^n \text{ is not } O(2^n)$

$$\begin{align} & \text{We evaluate both statements when } x \rightarrow \infty \quad \\[5pt] \end{align}$$

Block

Work 5.

$$\begin{align} \text{Prove that if } \mathcal{f}(x) \text{ is } O(x) \text{ then } \mathcal{f}(x) \text{ is also } O(x^2) \quad \\[5pt] \end{align}$$

Block

$$\begin{align} & \text{We have } \mathcal{f}(x) \in O(x) \quad \\[5pt] & \implies \text{There are some constants }\mathit{C}, k \text{ such that} \quad \\[5pt] & \forall x > k, \mathcal{f}(x) \leq \mathit{C} \cdot x \quad \\[5pt] & \text{We know that } x \leq x^2 \equiv \mathit{C} \cdot x \leq \mathit{C} \cdot x^2 \quad \\[5pt] & \implies \forall x > k, \mathcal{f}(x) \leq \mathit{C} \cdot x \leq \mathit{C} \cdot x^2 \equiv \mathcal{f}(x) \leq \mathit{C} \cdot x^2 \quad \\[5pt] & \text{Therefore } \mathcal{f}(x) \in O(x^2) \end{align}$$

Block

Work 7.

$$\begin{align} & \text{Give a big-}\mathit{O} \text{ estimate for the function} \quad \\[5pt] & \mathcal{f}(n) = 3n \log n! + (n^2 + 3) \log n \quad \\[5pt] \end{align}$$

Block

• Solution:

$$\begin{align} & \text{We want to find the Big-}\mathit{O} \text{ estimate of} \ \mathcal{f}(n) = 3n \log n! + (n^2 + 3) \log n \quad \\[5pt] \end{align}$$

Block

• Step 1: Estimate $( 3n \log n! )$

$$\begin{align} & \text{Using Stirling's approximation: } \log n! \sim n \log n - n \quad \\[5pt] & \therefore \log n! = O(n \log n) \quad \\[5pt] & \text{Multiply by } 3n: \quad \\[5pt] & 3n \log n! = O(n^2 \log n) \quad \\[5pt] \end{align}$$

Block

• Step 2: Estimate $( (n^2 + 3) \log n )$

$$\begin{align} & \text{We break this into two parts:} \quad \\[5pt] & n^2 \log n = O(n^2 \log n) \quad \\[5pt] & 3 \log n = O(\log n) \quad \\[5pt] & \text{Thus,} \ (n^2 + 3) \log n = O(n^2 \log n) + O(\log n) = O(n^2 \log n) \quad \\[5pt] \end{align}$$

Block

• Step 3: Combine the Results

$$\begin{align} & \mathcal{f}(n) = O(n^2 \log n) + O(n^2 \log n) = O(n^2 \log n) \quad \\[5pt] & \text{Therefore, the Big-}\mathit{O} \text{ estimate for } \mathcal{f}(n) \text{ is } O(n^2 \log n) \quad \\[5pt] \end{align}$$

Block

Work 8.

$$\begin{align} \text{Prove that } \mathcal{f} \text{ is } \Omega(g) \text{ if and only if } \mathcal{g} \text{ is } O(\mathcal{f}) \quad \\[5pt] \end{align}$$

Block

$$\begin{align} & \text{By definition, } \mathcal{f}(n) \in \Omega(g(n)) \text{ means:} \quad \\[5pt] & \exists \mathit{C} > 0, n_0 > 0 \text{ such that for all } n \geq n_0, g(n) \leq C \cdot f(n) \quad \\[5pt] & \text{This implies that } g(n) \in O(f(n)) \text{ by definition of } O \text{ notation.} \quad \\[5pt] & \text{Similarly, if } g(n) \in O(f(n)) \quad \\[5pt] & \text{ we can reverse the inequality to show } f(n) \in \Omega(g(n)). \quad \\[5pt] & \text{Thus, } \mathcal{f}(n) \in \Omega(g(n)) \iff \mathcal{g}(n) \in O(f(n)) \quad \\[5pt] \end{align}$$

Block

Work 10.

$$\begin{align} \text{Prove that } 1 + 2 + \ldots + n \text{ is } \Theta(n^2) \quad \\[5pt] \end{align}$$

Block

$$\begin{align} & \text{We want to show that the sum of the first } n \text{ positive integers is } \Theta(n^2). \quad \\[5pt] & \text{We know the formula for this sum:} \quad \\[5pt] & 1 + 2 + \ldots + n = \frac{n(n+1)}{2} \quad \\[5pt] & \text{This simplifies to } \frac{n^2 + n}{2}. \quad \\[5pt] & \text{As } n \to \infty, \frac{n^2 + n}{2} \sim \frac{n^2}{2}, \text{ so it grows like } O(n^2). \quad \\[5pt] & \text{Also, since } \frac{n^2 + n}{2} \geq \frac{n^2}{2} \text{ for large } n, \text{ the sum is } \Omega(n^2). \quad \\[5pt] & \text{Thus, we conclude that } 1 + 2 + \ldots + n = \Theta(n^2). \quad \\[5pt] \end{align}$$

Block

• References and Extras:
  • Algorithm I - Hoang Anh Duc - MIM - HUS - VNU
  • Work 2 (e) Complement 1: Quoc Dat Phung - Prove log(n!) is O(nlogn)
  • Work 2 (e) Complement 2: StackExchange - Mathematics
  • Work 2 (f) Complement: Quora
  • Work 2 (g) Complement 1: Proving log n is O(n) [Big-Oh Bootcamp]
  • Work 2 (g) Complement 2: StackExchange - Mathematics
  • Work 2 (h) Complement: StackExchange - Mathematics
  • ResearchGate - What does O(1) mean?
  • Filo - Explain what it means for a function to be O(1)
  • G4G - What does Constant Time Complexity or Big O(1) mean?
  • Work 5 Complement
  • UAG School of Computing - Big-O Notation
  • Kenneth H. Rosen - Discrete Mathematics and Its Applications.