Tutorial

Question 1

$O$-notation

For a given function $g(n)$, denoted by $O(g(n))$ the set of functions.

$O(g(n))$ = { $f(n)$: there exist positive constants $c$ and $n_0$ such that $0\le f(n)\le \mathrm{cg}(n)$ for all $n\ge n_0$}.

$\Omega$-notation

For a given function $g(n)$, denoted by $\Omega (g(n))$ the set of functions.

$\Omega (g(n))$ = { $f(n)$: there exist positive constants $c$ and $n_0$ such that $0\le \mathrm{cg}(n)\le f(n)$ for all $n\ge n_0$}.

$\Theta$-notation

For a given function $g(n)$, denoted by $\Theta (g(n))$ the set of functions.

$\Theta (g(n))$ = { $f(n)$: there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$ for all $n\ge n_0$}.

$o$-notation

For a given function, $g(n)$, we denote by $o(g(n))$ the set of functions.

$o(g(n))$ $=$ { $f(n)$: for any positive constant $c>0$, there exists a constant $n_0>0$ such that $0\le f(n)<\mathrm{cg}(n)$ for all $n\ge n_0$}.

The implication of this, is that $f(n)$ becomes insignificant relative to $g(n)$ as $n$ approaches infinity:

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

$\omega$-notation

For a given function, $g(n)$, we denote by $\omega (g(n))$ the set of functions.

$\omega (g(n))$ $=$ { $f(n)$: for any positive constant $c>0$, there exists a constant $n_0>0$ such that $0\le cg(n)<f(n)$ for all $n\ge n_0$}.

The implication of this is that $g(n)$ becomes insignificant relative to $f(n)$ as $n$ approaches infinity:

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

Question 2

The difference between $O$ and $o$ is that $O$ represents an upper bound of the solution for a problem, which may also be the tight bound of solving that problem, while $o$ clearly indicates that it is an upper bound but definitely not the tight bound.

For example, $2n=o(n^2)$ but $2n^2\ne o(n^2)$.

For the Omegas...

For example $n^2/2=\omega (n)$ but $n^2/2\ne \omega (n^2)$.

Question 3

First, work out that the following is actually a constant...

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{n^{\frac{1}{{\log }_{2}n}}}& =\hfill & n^{\frac{\lg 2}{\lg n}}\hfill \\ \multicolumn{1}{c}{}& =\hfill & n^{{\log }_{n}2}\hfill \\ \multicolumn{1}{c}{}& =\hfill & 2^{{\log }_{n}n}\hfill \\ \multicolumn{1}{c}{}& =\hfill & 2^1\hfill \\ \multicolumn{1}{c}{}& =\hfill & 2\hfill \end{array}}$

(5) $n^{1/\log n}$	$\to$	$2$
(4) ${\log }^{*}n{\log }^{2}n$	$\to$	$\log n$
(6) $\sqrt{n^{1/3}\log n}$	$\to$	$n^{1/6}$
(8) $\sqrt{n}$	$\to$	$n^{1/2}$
(2) $n^{3/2}{\log }^{4}n$	$\to$	$n^{3/2}$
(1) $n^2\log n$	$\to$	$n^2$
(7) $n^{\log \log n}$	$\to$	$n^{\log \log n}$
(3) $3^{0.7n}$	$\to$	$3^n$

Note that "Log star of n" is iterated logarithm.

${\log }^{*}n=\text{min}\{i\ge 0:{\log }^{i}n\le 1\}$

Question 4

1. (DIVIDE) Pick an element $x=a_i$ to be the pivot element. Usually the first element $a_1$ is picked.
2. (DIVIDE) Partition the sequence into two disjoint subsequences:
   $S_1=\{a_i:a_i\le x\}$, and
   $S_2=\{a_j:a_j>x\}$.
3. (CONQUER) Sort $S_1$ and $S_2$ recursively using quicksort.
4. (MERGE) Merge the sorted $S_1$, $\{x\}$, and $S_2$. The original sequence is sorted.

Question 5

The four techniques for bounding summations are as follows.

1. Mathematical induction
   What is mathematical induction? For example, binding the series: $1+2+3+\dots +n$
   
   

   ${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{P(n)\text{ says: }1+2+3+\dots +n}& =\hfill & \frac{n(n+1)}{2}\hfill \end{array}}$

   
   
   If $P(n)$ is true, is $P(n+1)$ true?
   
   

   ${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{P(n+1)\text{ says: }1+2+3+\dots +n+(n+1)}& =\hfill & \frac{n(n+1)}{2}+(n+1)\hfill \\ \multicolumn{1}{c}{}& =\hfill & \frac{(n+1)(n+2)}{2}\hfill \\ \multicolumn{1}{c}{}& =\hfill & \frac{(n+1)((n+1)+1)}{2}\hfill \end{array}}$

   
   
   Therefore $P(n)\Rightarrow P(n+1)$.
   Now, show our base case. $P(1)$ is true because $1=\frac{1(1+1)}{2}=1$. And since $P(1)$ is true, $P(2)$ must be true, so $P(3)$ is true, and so on...
2. Splitting summations
   For example, finding the lower bound.
   We can change $k$ to $n$ and find the upper bound:
   
   

   ${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{\sum _{k=1}^{n}k}& \le \hfill & \sum _{k=1}^{n}n\hfill \\ \multicolumn{1}{c}{}& =\hfill & n^2\hfill \\ \multicolumn{1}{c}{}& =\hfill & O(n^2)\hfill \end{array}}$

   
   
   To find the lower bound we split the summation:
   
   

   ${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{\sum _{k=1}^{n}k}& =\hfill & \sum _{k=1}^{n/2}k+\sum _{k=n/2+1}^{n}k\hfill \\ \multicolumn{1}{c}{}& \ge \hfill & \sum _{k=1}^{n/2}0+\sum _{k=n/2+1}^{n}n/2\hfill \\ \multicolumn{1}{c}{}& =\hfill & \frac{n^2}{4}\hfill \\ \multicolumn{1}{c}{}& =\hfill & \Omega (n^2)\hfill \end{array}}$

   
   
3. Approximation by integrals
   For example, if we have $\sum _{x=p}^{q}f(x)$, then the sum really is the area under the curve $f(x)$ for $p\le x\le q$. We can use integration to find the area under a curve. Thus the summation is approximately equal to ${\int }_p^{q}f(x)$.
4. Bounding terms
   We now apply the bounding terms to show the upper bound of
   
   

   ${\displaystyle \sum _{k=1}^{\infty }\frac{k}{5^k}}$

   
   
   Let $a_k=\frac{k}{5^k}$
   Then...
   
   

   ${\displaystyle \frac{a_{k+1}}{a_k}=\frac{k+1}{5^{k+1}}\times \frac{5^k}{k}=\frac{k+1}{5k}}$

   
   
   This is maximum when $k=1$, so...
   
   

   ${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{r}& \le \hfill & \frac{1+1}{5}\hfill \\ \multicolumn{1}{c}{r}& \le \hfill & \frac{2}{5}\hfill \end{array}}$

   
   
   Given that the first term $a_1=1/5$, $\sum _{k=1}^{\infty }\frac{k}{5^k}$ can be bounded by the sum to infinity of the geometric series.
   
   

   ${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{\sum _{k=1}^{\infty }\frac{k}{5^k}}& \le \hfill & \frac{1}{5}\times \frac{1}{1-\frac{2}{5}}\hfill \\ \multicolumn{1}{c}{}& =\hfill & \frac{1}{5}\times \frac{1}{\frac{3}{5}}\hfill \\ \multicolumn{1}{c}{}& =\hfill & \frac{1}{3}\hfill \end{array}}$

   
   

Question 6

• Substitution method: guess a bound and then use mathematical induction to prove that the guess is correct.
• Iteration method: convert the recurrence into a summation and then use the techniques for bounding summations to solve the recurrence.

Question 6(a)

Using the iterative method...

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& =\hfill & n^{4/3}+T(n/3)\hfill \\ \multicolumn{1}{c}{}& =\hfill & n^{4/3}+(\frac{n}{3}{)}^{4/3}+T(\frac{n}{3^2})\hfill \\ \multicolumn{1}{c}{}& =\hfill & n^{4/3}+(\frac{n}{3}{)}^{4/3}+(\frac{n}{3^2}{)}^{4/3}+T(\frac{n}{3^3})\hfill \\ \multicolumn{1}{c}{}& =\hfill & n^{4/3}+(\frac{n}{3}{)}^{4/3}+(\frac{n}{3^2}{)}^{4/3}+\dots +(\frac{n}{3^k}{)}^{4/3}\hfill \end{array}}$

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& =\hfill & n^{4/3}\sum _{i=0}^k{\left(\frac{1}{3^i}\right)}^{4/3}\hfill \\ \multicolumn{1}{c}{}& =\hfill & n^{4/3}\sum _{i=0}^k{\left(\frac{1}{3^{4/3}}\right)}^i\hfill \\ \multicolumn{1}{c}{}& <\hfill & n^{4/3}\sum _{i=0}^{\infty }{\left(\frac{1}{3^{4/3}}\right)}^i\hfill \\ \multicolumn{1}{c}{}& <\hfill & n^{4/3}\frac{1}{1-\frac{1}{3^{4/3}}}\hfill \end{array}}$

Let constant $c=\frac{1}{1-\frac{1}{3^{4/3}}}$

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& <\hfill & c{n}^{4/3}\hfill \\ \multicolumn{1}{c}{}& =\hfill & O(n^{4/3})\hfill \end{array}}$

If you want to find k...

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{\frac{n}{3^k}}& =\hfill & 1\hfill \\ \multicolumn{1}{c}{k}& =\hfill & {\log }_{3}n\hfill \end{array}}$

Question 6(b)

Using the substitution method, first...

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{n/4}& \ge \hfill & n/5+57\hfill \\ \multicolumn{1}{c}{n}& \ge \hfill & 1140\hfill \end{array}}$

Since $n/4\ge n/5+57$ when $n\ge 1140$, $T(n/4)$ will dominate $T(n/5+57)$ when $n\ge 1140$. So we simplify the recurrence into:

${\displaystyle T(n)\le 2T(n/4)+{\log }_{2}n}$

GUESS 1: Now we guess that the solution is:

${\displaystyle T(n)\le c\sqrt{n}}$

Assuming that this holds for $T(n/4)$:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n/4)}& \le \hfill & c\sqrt{n/4}\hfill \\ \multicolumn{1}{c}{}& =\hfill & \frac{1}{2}c\sqrt{n}\hfill \end{array}}$

Substitute this into our original $T(n)$:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& \le \hfill & 2\left(\frac{1}{2}c\sqrt{n}\right)+{\log }_{2}n\hfill \\ \multicolumn{1}{c}{}& =\hfill & c\sqrt{n}+{\log }_{2}n\hfill \end{array}}$

This doesn't agree with our guess.

GUESS 2: Revise our guess to $T(n)\le c\sqrt{n}+b{\log }_{2}n$

Assume $T(n/4)\le c\sqrt{n/4}+b{\log }_2(n/4)$

Substitute:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& \le \hfill & 2(c\sqrt{n/4}+b{\log }_2(n/4))+{\log }_{2}n\hfill \\ \multicolumn{1}{c}{}& =\hfill & c\sqrt{n}+2b{\log }_{2}n-2b{\log }_{2}4+{\log }_{2}n\hfill \\ \multicolumn{1}{c}{}& =\hfill & c\sqrt{n}+(2b+1){\log }_{2}n-4b\hfill \end{array}}$

Still doesn't agree with our guess.

GUESS 3: Revise our guess to $T(n)\le c\sqrt{n}+b{\log }_{2}n+a$

Assume $T(n/4)\le c\sqrt{n/4}+b{\log }_2(n/4)+a$

Substitute:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& \le \hfill & 2(c\sqrt{n/4}+b{\log }_2(n/4)+a)+{\log }_{2}n\hfill \\ \multicolumn{1}{c}{}& =\hfill & c\sqrt{n}+2b{\log }_{2}n-2b{\log }_{2}4+{\log }_{2}n+2a\hfill \\ \multicolumn{1}{c}{}& =\hfill & c\sqrt{n}+(2b+1){\log }_{2}n+2a-4b\hfill \end{array}}$

Since this is the same form as our guess, we solve for $b$ and $a$.

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{2b+1}& =\hfill & b\hfill \\ \multicolumn{1}{c}{b}& =\hfill & -1\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill \\ \multicolumn{1}{c}{2a-4b}& =\hfill & a\hfill \\ \multicolumn{1}{c}{a}& =\hfill & 4b\hfill \\ \multicolumn{1}{c}{a}& =\hfill & -4\hfill \end{array}}$

Thus, the inequality holds when $b=-1$ and $a=-4$.

For all $n<1140$, let the $T(n)$ be bounded by a constant $R$.

Solve for $c$ when $n=4096$:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(4096)}& \le \hfill & c\sqrt{4096}-{\log }_{2}4096-4\hfill \\ \multicolumn{1}{c}{2T(1024)+{\log }_{2}4096}& \le \hfill & c\sqrt{4096}-{\log }_{2}4096-4\hfill \\ \multicolumn{1}{c}{2R+12}& \le \hfill & 64c-12-4\hfill \\ \multicolumn{1}{c}{c}& \ge \hfill & \frac{2R+28}{64}\hfill \end{array}}$

Thus, $0\le T(n)\le c\sqrt{n}-{\log }_{2}n-4$ when $c\ge \frac{2R+28}{64}$ for all $n\ge 1140$

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

Question 6(c) iterative

Using the iterative method...

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& =\hfill & 3n+T(\lfloor \sqrt{n}\rfloor )\hfill \\ \multicolumn{1}{c}{}& =\hfill & 3n+3n^{1/2}+T(\lfloor n^{1/4}\rfloor )\hfill \\ \multicolumn{1}{c}{}& =\hfill & 3n+3n^{(\frac{1}{2})}+3n^{(\frac{1}{2}{)}^2}+\dots +3n^{(\frac{1}{2}{)}^k}\hfill \end{array}}$

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{k}& =\hfill & \text{no. of times we can square root}n\text{until it is 2}\hfill \\ \multicolumn{1}{c}{n^{{\left(\frac{1}{2}\right)}^k}}& =\hfill & 2\hfill \\ \multicolumn{1}{c}{{\left(\frac{1}{2}\right)}^k\lg n}& =\hfill & \lg 2\hfill \\ \multicolumn{1}{c}{{\left(\frac{1}{2}\right)}^k}& =\hfill & \frac{\lg 2}{\lg n}\hfill \\ \multicolumn{1}{c}{2^k}& =\hfill & \lg n\hfill \\ \multicolumn{1}{c}{k\lg 2}& =\hfill & \lg \lg n\hfill \\ \multicolumn{1}{c}{k}& =\hfill & \lg \lg n\hfill \end{array}}$

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(n)}& \le \hfill & 3n\times (k+1)\hfill \\ \multicolumn{1}{c}{}& \le \hfill & 3n\times (\lg \lg n+1)\hfill \\ \multicolumn{1}{c}{}& \le \hfill & 3n\lg \lg n+3n\hfill \\ \multicolumn{1}{c}{}& =\hfill & O(n\lg \lg n)\hfill \end{array}}$

Question 6(c) changing variables

An alternative method is to use "changing variables" together with the iterative method.

Let $n=2^m$.

Substituting this into the recurrence, we get:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{T(2^m)}& =\hfill & T(2^{m/2})+3\times 2^m\hfill \\ \multicolumn{1}{c}{}& \hfill & \text{Note that square root is essentially halving the power.}\hfill \end{array}}$

Rename $S(m)=T(2^m)$:

${\displaystyle S(m)=S(m/2)+3\times 2^m}$

This is possible because now we have changed the "problem size" variable to $m$. Note that work done at each level of the recursion is still $3\times 2^m=3n$. So using the iterative method to solve $S(m)$...

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{S(m)}& =\hfill & S(m/2)+3\times 2^m\hfill \\ \multicolumn{1}{c}{}& =\hfill & 3\times 2^m+3\times 2^{m/2}+S(m/2^2)\hfill \\ \multicolumn{1}{c}{}& =\hfill & 3\times 2^m+3\times 2^{m/2}+3\times 2^{m/2^2}+\dots +3\times 2^{m/2^k}\hfill \\ \multicolumn{1}{c}{}& =\hfill & 3\sum _{i=0}^k{2}^{m/2^i}\hfill \end{array}}$

Find $k$:

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{2^{m/2^k}}& =\hfill & 2\hfill \\ \multicolumn{1}{c}{m/2^k}& =\hfill & 1\hfill \\ \multicolumn{1}{c}{k}& =\hfill & {\log }_{2}m\hfill \end{array}}$

Since the biggest element in the summation is when $i=0$, we can bind the summation by replacing $2^{m/2^i}$ with $2^m$.

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{S(m)}& \le \hfill & 3\times 2^m{\log }_{2}m\hfill \\ \multicolumn{1}{c}{}& =\hfill & O(2^m{\log }_{2}m)\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill \\ \multicolumn{1}{c}{T(n)}& =\hfill & T(2^m)\hfill \\ \multicolumn{1}{c}{}& =\hfill & S(m)\hfill \\ \multicolumn{1}{c}{}& =\hfill & O(2^m{\log }_{2}m)\hfill \\ \multicolumn{1}{c}{}& =\hfill & O(n{\log }_2{\log }_{2}n)\hfill \end{array}}$