# Tutorial

## Question 1

Review the definitions of the basic notations such as $\Theta$, $O$, $\Omega$, $o$, and $\omega$.
$O$-notation
For a given function $g\left(n\right)$, denoted by $O\left(g\left(n\right)\right)$ the set of functions.
$O\left(g\left(n\right)\right)$ = { $f\left(n\right)$: there exist positive constants $c$ and ${n}_{0}$ such that $0\le f\left(n\right)\le \mathrm{cg}\left(n\right)$ for all $n\ge {n}_{0}$}.
$\Omega$-notation
For a given function $g\left(n\right)$, denoted by $\Omega \left(g\left(n\right)\right)$ the set of functions.
$\Omega \left(g\left(n\right)\right)$ = { $f\left(n\right)$: there exist positive constants $c$ and ${n}_{0}$ such that $0\le \mathrm{cg}\left(n\right)\le f\left(n\right)$ for all $n\ge {n}_{0}$}.
$\Theta$-notation
For a given function $g\left(n\right)$, denoted by $\Theta \left(g\left(n\right)\right)$ the set of functions.
$\Theta \left(g\left(n\right)\right)$ = { $f\left(n\right)$: there exist positive constants ${c}_{1}$, ${c}_{2}$, and ${n}_{0}$ such that $0\le {c}_{1}g\left(n\right)\le f\left(n\right)\le {c}_{2}g\left(n\right)$ for all $n\ge {n}_{0}$}.
$o$-notation
For a given function, $g\left(n\right)$, we denote by $o\left(g\left(n\right)\right)$ the set of functions.
$o\left(g\left(n\right)\right)$ $=$ { $f\left(n\right)$: for any positive constant $c>0$, there exists a constant ${n}_{0}>0$ such that $0\le f\left(n\right)<\mathrm{cg}\left(n\right)$ for all $n\ge {n}_{0}$}.
The implication of this, is that $f\left(n\right)$ becomes insignificant relative to $g\left(n\right)$ as $n$ approaches infinity:

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

$\omega$-notation
For a given function, $g\left(n\right)$, we denote by $\omega \left(g\left(n\right)\right)$ the set of functions.
$\omega \left(g\left(n\right)\right)$ $=$ { $f\left(n\right)$: for any positive constant $c>0$, there exists a constant ${n}_{0}>0$ such that $0\le cg\left(n\right) for all $n\ge {n}_{0}$}.
The implication of this is that $g\left(n\right)$ becomes insignificant relative to $f\left(n\right)$ as $n$ approaches infinity:

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

## Question 2

What is the difference between $O$ and $o$ as well as $\Omega$ and $\omega$?
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\left({n}^{2}\right)$ but $2{n}^{2}\ne o\left({n}^{2}\right)$.
For the Omegas...
For example ${n}^{2}/2=\omega \left(n\right)$ but ${n}^{2}/2\ne \omega \left({n}^{2}\right)$.

## Question 3

Rank the following functions in the order of growth: ${n}^{2}\mathrm{log}n$, ${n}^{3/2}{\mathrm{log}}^{4}n$, ${3}^{0.7n}$, ${\mathrm{log}}^{*}n{\mathrm{log}}^{2}n$, ${n}^{1/\mathrm{log}n}$, $\sqrt{{n}^{1/3}\mathrm{log}n}$, ${n}^{\mathrm{log}\mathrm{log}n}$, $\sqrt{n}$
First, work out that the following is actually a constant...

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

 (5) ${n}^{1/\mathrm{log}n}$ $\to$ $2$ (4) ${\mathrm{log}}^{*}n{\mathrm{log}}^{2}n$ $\to$ $\mathrm{log}n$ (6) $\sqrt{{n}^{1/3}\mathrm{log}n}$ $\to$ ${n}^{1/6}$ (8) $\sqrt{n}$ $\to$ ${n}^{1/2}$ (2) ${n}^{3/2}{\mathrm{log}}^{4}n$ $\to$ ${n}^{3/2}$ (1) ${n}^{2}\mathrm{log}n$ $\to$ ${n}^{2}$ (7) ${n}^{\mathrm{log}\mathrm{log}n}$ $\to$ ${n}^{\mathrm{log}\mathrm{log}n}$ (3) ${3}^{0.7n}$ $\to$ ${3}^{n}$
Note that "Log star of n" is iterated logarithm.
${\mathrm{log}}^{*}n=\text{min}\left\{i\ge 0:{\mathrm{log}}^{i}n\le 1\right\}$

## Question 4

Use the divide-and-conquer paradigm to explain the basic steps of the quicksort algorithm.
The divide-and-conquer strategy divides a problem $A$ into a number of subproblems of roughly equal sizes. Then each subproblem is solved recursively. The base case being a subproblem that is small enough to solve without further dividing. Next, the solutions of the subproblems are combined to obtain the solution for the original problem.
For the case of quicksort:
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}=\left\{{a}_{i}:{a}_{i}\le x\right\}$, and
${S}_{2}=\left\{{a}_{j}:{a}_{j}>x\right\}$.
3. (CONQUER) Sort ${S}_{1}$ and ${S}_{2}$ recursively using quicksort.
4. (MERGE) Merge the sorted ${S}_{1}$, $\left\{x\right\}$, and ${S}_{2}$. The original sequence is sorted.

## Question 5

Review the four techniques for bounding the summations. Use one of the introduced techniques to bound $\sum _{k=1}^{\infty }\frac{k}{{5}^{k}}$.
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$

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

Therefore $P\left(n\right)⇒P\left(n+1\right)$.
Now, show our base case. $P\left(1\right)$ is true because $1=\frac{1\left(1+1\right)}{2}=1$. And since $P\left(1\right)$ is true, $P\left(2\right)$ must be true, so $P\left(3\right)$ 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:

 $\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\left({n}^{2}\right)\hfill \end{array}$

To find the lower bound we split the summation:

 $\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 \left({n}^{2}\right)\hfill \end{array}$

3. Approximation by integrals
For example, if we have $\sum _{x=p}^{q}f\left(x\right)$, then the sum really is the area under the curve $f\left(x\right)$ 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\left(x\right)$.
4. Bounding terms
We now apply the bounding terms to show the upper bound of

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

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

 $\frac{{a}_{k+1}}{{a}_{k}}=\frac{k+1}{{5}^{k+1}}×\frac{{5}^{k}}{k}=\frac{k+1}{5k}$

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

 $\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.

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

## Question 6

Review the two approaches for solving recurrences, and apply them to solve the following recurrences.
• 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)

$T\left(n\right)=T\left(n/3\right)+{n}^{4/3}$
Using the iterative method...

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

 $\begin{array}{ccc}\multicolumn{1}{c}{T\left(n\right)}& =\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}}}$

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

If you want to find k...

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

## Question 6(b)

$T\left(n\right)\le T\left(n/4\right)+T\left(n/5+57\right)+{\mathrm{log}}_{2}n$
Using the substitution method, first...

 $\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\left(n/4\right)$ will dominate $T\left(n/5+57\right)$ when $n\ge 1140$. So we simplify the recurrence into:

 $T\left(n\right)\le 2T\left(n/4\right)+{\mathrm{log}}_{2}n$

GUESS 1: Now we guess that the solution is:

 $T\left(n\right)\le c\sqrt{n}$

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

 $\begin{array}{ccc}\multicolumn{1}{c}{T\left(n/4\right)}& \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\left(n\right)$:

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

This doesn't agree with our guess.
GUESS 2: Revise our guess to $T\left(n\right)\le c\sqrt{n}+b{\mathrm{log}}_{2}n$
Assume $T\left(n/4\right)\le c\sqrt{n/4}+b{\mathrm{log}}_{2}\left(n/4\right)$
Substitute:

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

Still doesn't agree with our guess.
GUESS 3: Revise our guess to $T\left(n\right)\le c\sqrt{n}+b{\mathrm{log}}_{2}n+a$
Assume $T\left(n/4\right)\le c\sqrt{n/4}+b{\mathrm{log}}_{2}\left(n/4\right)+a$
Substitute:

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

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

 $\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\left(n\right)$ be bounded by a constant $R$.
Solve for $c$ when $n=4096$:

 $\begin{array}{ccc}\multicolumn{1}{c}{T\left(4096\right)}& \le \hfill & c\sqrt{4096}-{\mathrm{log}}_{2}4096-4\hfill \\ \multicolumn{1}{c}{2T\left(1024\right)+{\mathrm{log}}_{2}4096}& \le \hfill & c\sqrt{4096}-{\mathrm{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\left(n\right)\le c\sqrt{n}-{\mathrm{log}}_{2}n-4$ when $c\ge \frac{2R+28}{64}$ for all $n\ge 1140$
$T\left(n\right)=O\left(\sqrt{n}\right)$

## Question 6(c) iterative

$T\left(n\right)=T\left(⌊\sqrt{n}⌋\right)+3n$
Using the iterative method...

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

 $\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}\mathrm{lg}n}& =\hfill & \mathrm{lg}2\hfill \\ \multicolumn{1}{c}{{\left(\frac{1}{2}\right)}^{k}}& =\hfill & \frac{\mathrm{lg}2}{\mathrm{lg}n}\hfill \\ \multicolumn{1}{c}{{2}^{k}}& =\hfill & \mathrm{lg}n\hfill \\ \multicolumn{1}{c}{k\mathrm{lg}2}& =\hfill & \mathrm{lg}\mathrm{lg}n\hfill \\ \multicolumn{1}{c}{k}& =\hfill & \mathrm{lg}\mathrm{lg}n\hfill \end{array}$

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

## Question 6(c) changing variables

$T\left(n\right)=T\left(⌊\sqrt{n}⌋\right)+3n$
An alternative method is to use "changing variables" together with the iterative method.
Let $n={2}^{m}$.
Substituting this into the recurrence, we get:

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

Rename $S\left(m\right)=T\left({2}^{m}\right)$:

 $S\left(m\right)=S\left(m/2\right)+3×{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×{2}^{m}=3n$. So using the iterative method to solve $S\left(m\right)$...

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

Find $k$:

 $\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 & {\mathrm{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}$.

 $\begin{array}{ccc}\multicolumn{1}{c}{S\left(m\right)}& \le \hfill & 3×{2}^{m}{\mathrm{log}}_{2}m\hfill \\ \multicolumn{1}{c}{}& =\hfill & O\left({2}^{m}{\mathrm{log}}_{2}m\right)\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill \\ \multicolumn{1}{c}{T\left(n\right)}& =\hfill & T\left({2}^{m}\right)\hfill \\ \multicolumn{1}{c}{}& =\hfill & S\left(m\right)\hfill \\ \multicolumn{1}{c}{}& =\hfill & O\left({2}^{m}{\mathrm{log}}_{2}m\right)\hfill \\ \multicolumn{1}{c}{}& =\hfill & O\left(n{\mathrm{log}}_{2}{\mathrm{log}}_{2}n\right)\hfill \end{array}$

File translated from TEX by TTM, version 3.67.
On 31 Mar 2006, 18:12.