Efficiency of a Program

Click here for a blank version of this page for practice.

What is an algorithm?

• A step by step process that solves a problem
• Gives the correct output for all inputs
• Complete the process in finite time

Real time: Can be measured by having a virtual stopwatch to count how long a program takes to run. Will get different results on different machines.

Scale/Growth Rate: Count the amount of iterations the loops take. Will get same results on different machines.

We can categorize the growth rate into an asymptotic complexity class:

Name	Function
Constant	$n^2$	Slower growth rate
Logarithmic	$\log n$
Linear	$n$
Poly-logarithmic	$lo{g}^{k}n$
Quadratic	$n^2$
Cubic	$n^3$
Exponential	$C^n$	Higher growth rate

---

Big O notation

Consider the equation:
$g(n)=O(f(n))$
In this case, $=$ has the meaning of $\in$.
Thus, it translates to:

$g(n)$ is in the set of all functions whose growth rate is at most $f(n)$.

In order to determine the validity of that statement, prove that:

$$\begin{gathered} g(n)\le C\cdot f(n) \\ \text{Where }C>0\text{ and }{n}_0>0 \\ \text{For all }n \end{gathered}$$

$f(n)$ can be any function, but it is proper to use one of the asymptotic complexity classes.

Examples

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}$$

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

$$\begin{gathered} 2n^2+7\le C\cdot n \\ \text{Suppose }C=10\text{ and }{n}_0=1 \end{gathered}$$

$$\text{Thus, the statement does not hold at large values of }n\text{.}$$

---

Big Ω Notation

Recall that $O(f(n))$ represents an upper bound.

$\Omega (f(n))$ represents a lower bound.

In order to prove if $g(n)=\Omega (f(n))$:

$$\begin{gathered} g(n)\ge C\cdot f(n) \\ \text{Where }C>0\text{ and }{n}_0>0 \\ \text{For all }n \end{gathered}$$

Examples

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.} \\ \text{However, this is a weak statement and can be improved (see below)} \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.} \\ \text{This statement is too much and is no longer valid} \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 and strong.} \end{gathered}$$

---

Big Θ Notation

Recall that $O(f(n))$ represents an upper bound and $\Omega (f(n))$ represents a lower bound.

$\Theta (f(n))$ represents an exact bound. In other words,

$$\begin{gathered} g(n)=\Theta (f(n)) \\ \iff \\ g(n)=O(f(n))\wedge g(n)=\Omega (f(n)) \end{gathered}$$

Examples

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

In order to compare the growth rate of two functions, we can also use limits.
This is a more matematical and precise method.

$$\begin{gathered} \underset{n\to \infty }{\lim }\frac{g(n)}{f(n)}=\underset{n\to \infty }{\lim }\frac{g^{\prime }(n)}{f^{\prime }(n)}=\underset{n\to \infty }{\lim }\frac{g^{\prime \prime }(n)}{f^{\prime \prime }(n)}=L \\ L=\infty ⟹g(n)>f(n) \\ L=C>0⟹g(n)=f(n) \\ L=0⟹g(n)<f(n) \end{gathered}$$

Recall

If the limit of an expression results in an indeterminate form:

$$\underset{n\to \infty }{\lim }\frac{g(n)}{f(n)}=\frac{0}{0}\text{or}\underset{n\to \infty }{\lim }\frac{g(n)}{f(n)}=\frac{\infty }{\infty }$$

Then you may take the derivative of the numerator and denominator and attempt to find the limit again:

$$\underset{n\to \infty }{\lim }\frac{g(n)}{f(n)}=\underset{n\to \infty }{\lim }\frac{g^{\prime }(n)}{f^{\prime }(n)}$$

Examples

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}$$

---

Logarithms

Consider the equation $\Theta (\log n)$.
Typically, $\log n$ implies a base of $10$.

Is this still true?

Recall

The base of a log can be changed via the formula:

$${\log }_{b}a=\frac{{\log }_{x}a}{{\log }_{x}b}$$

Therefore, $\Theta (\log n)$ contains all log functions of any base, since we can easily convert from one to another.