Efficiency of a Program - Practice

Big O notation

Prove or disprove the following statements.

(a) $n=O(n)$

$$\begin{gathered} n\le C\cdot n \\ \text{Suppose }C=1\text{ and }{n}_0=1 \\ n\le 1\cdot n⟹n\le n \\ \text{Thus, the statement is true.} \end{gathered}$$

(b) $5n=O(n)$

$$\begin{gathered} 5n\le C\cdot n \\ \text{Suppose }C=5\text{ and }{n}_0=1 \\ 5n\le 5\cdot n⟹5n\le 5n \\ \text{Thus, the statement is true.} \end{gathered}$$

(c) $10n+3=O(n)$

$$\begin{gathered} 10n+3\le C\cdot n \\ \text{Suppose }C=13\text{ and }{n}_0=1 \\ 10n+3\le 13n \\ ⟹10n+3\le 10n+3n \\ ⟹3\le 3n \\ \text{Thus, the statement is true.} \end{gathered}$$

(d) $\sqrt{n}=O(n)$

$$\begin{gathered} \sqrt{n}\le C\cdot n \\ \text{Suppose }C=1\text{ and }{n}_0=1 \\ \sqrt{n}\le \sqrt{n}\cdot \sqrt{n} \\ ⟹1\le \sqrt{n} \\ \text{Thus, the statement is true.} \end{gathered}$$

(e) $2n^2+7=O(n^3)$

$$\begin{gathered} 2n^2+7\le C\cdot n^3 \\ \text{Suppose }C=9\text{ and }{n}_0=1 \\ 2n^2+7\le 9n^3 \\ \text{Thus, the statement is true.} \end{gathered}$$

(f) $2n^2+7=O(n^2)$

$$\begin{gathered} 2n^2+7\le C\cdot n^2 \\ \text{Suppose }C=9\text{ and }{n}_0=1 \\ 2n^2+7\le 9\cdot n^2⟹2n^2+7\le 9n^2 \\ \text{Thus, the statement is true.} \end{gathered}$$

---

Big Ω Notation

Prove or disprove the following statements.

(h) $3n+2=\Omega (n)$

$$\begin{gathered} 3n+2\ge C\cdot n \\ \text{Suppose }C=3\text{ and }{n}_0=1 \\ 3n+2\ge 3n \\ \text{Thus, the statement is true.} \end{gathered}$$

(i) $n^2+13n=\Omega (n)$

$$\begin{gathered} n^2+13n\ge C\cdot n \\ \text{Suppose }C=1\text{ and }{n}_0=1 \\ {n}^2+13n\ge n \\ \text{Thus, the statement is true.} \end{gathered}$$

(j) $n^2+13n=\Omega (n^3)$

$$\begin{gathered} n^2+13n\ge C\cdot n^3 \\ \text{Suppose }C=1,000,000\text{ and }{n}_0=1 \\ {n}^2+13n\ge 1,000,000n \\ \text{Thus, the statement is false.} \end{gathered}$$

(k) $n^2+13n=\Omega (n^2)$

$$\begin{gathered} n^2+13n\ge C\cdot n^2 \\ \text{Suppose }C=1\text{ and }{n}_0=1 \\ {n}^2+13n\ge n^2 \\ \text{Thus, the statement is true.} \end{gathered}$$

---

Big Θ Notation

Prove or disprove the following statements.

(l) $13n+2=\Theta (n)$

$$\begin{gathered} 13n+2=O(n)\text{ is true} \\ 13n+2=\Omega (n)\text{ is true} \\ \text{Thus, the statement is true.} \end{gathered}$$

(m) $13n+2=\Theta (n^2)$

$$\begin{gathered} 13n+2=O(n^2)\text{ is true} \\ 13n+2=\Omega (n^2)\text{ is false} \\ \text{Thus, the statement is false.} \end{gathered}$$

(n) $13n+2=\Theta (\sqrt{n})$

$$\begin{gathered} 13n+2=O(\sqrt{n})\text{ is false} \\ 13n+2=\Omega (\sqrt{n})\text{ is true} \\ \text{Thus, the statement is false.} \end{gathered}$$

---

Comparing Growth Rates

Prove or disprove the following statements.

(o) $2n^2+7=O(n)$

$$\begin{gathered} L=\underset{n\to \infty }{\lim }\frac{2n^2+7}{n}=\underset{n\to \infty }{\lim }\frac{n(2n+\frac{7}{n})}{n}=\underset{n\to \infty }{\lim }(2n+\frac{7}{n})=\infty \\ \text{Since }L=\infty ⟹g(n)>f(n)\text{,} \\ 2n^2+7\text{ is asymptotically larger than }n \\ \text{Thus, the statement is false.} \end{gathered}$$

(p) $2n^2+7=O(n^3)$

$$\begin{gathered} L=\underset{n\to \infty }{\lim }\frac{2n^2+7}{n^3}=\underset{n\to \infty }{\lim }\frac{4n}{3n^2}=\underset{n\to \infty }{\lim }\frac{4}{3n}=\frac{4}{\infty }=0 \\ \text{Since }L=0⟹g(n)<f(n)\text{,} \\ {n}^3\text{ is asymptotically larger than }2n^2+7 \\ \text{Thus, the statement is true.} \end{gathered}$$

(q) $2n^2+7=O(n^2)$

$$\begin{gathered} L=\underset{n\to \infty }{\lim }\frac{2n^2+7)}{n^2}=\underset{n\to \infty }{\lim }\frac{4n}{2n}=2 \\ \text{Since }L=C=2>0⟹g(n)=f(n)\text{,} \\ 2n^2+7\text{ and }{n}^2\text{ have the same growth rate } \\ \text{Thus, the statement is true.} \end{gathered}$$