# Week 3. Complexity Analysis

## Algorithms and Data Structures

### 4 Week 3. Complexity Analysis

Reading 3 Goodrich, Tamassia, & Goldwasser: Chapter 4

#### 4.1 Key Concepts

##### 4.1.1 Complexity

- 1.
- Induction and Deduction
- 2.
- Common functions with examples
- 3.
- Algorithm Theory focuses on infinitely large datasets: asymptotics
- 4.
- Big-O
- 5.
- Recursion and loop
- 6.
- Mathematical Induction and Loop Invariants
- 7.
- Computing Model

##### 4.1.2 Recursion

- 1.
**TODO**video on Induction and recursion

#### 4.2 Projects and Exercises

This week, I ask you not to start with the compulsory projects. The Wednesday Group Work section contains two warm-up problems, and then a discussion exercise which I want to discuss in the plenary debrief, after your group discussion.

You should be able to complete those three problems in the group session, and you may have time to proceed with the compulsory projects.

##### 4.2.1 Wednesday Group Work

Problem 4.1 (Goodrich *et al* R-4.1 rephrased) The number of operations executed by algortihms
A and B is $8n\mathrm{log}n$
and $2{n}^{3}$,
respectively. Determine ${n}_{0}$
such that A| is better than B for $n\ge {n}_{0}$

Problem 4.2 (Goodrich *et al* R-4.7 rephrased) Order the following functions by asymptotic
growth rate:

$$4n\mathrm{log}n+2n,{2}^{65},{2}^{\mathrm{log}n},4n+100\mathrm{log}n,4n,1.{1}^{n},{n}^{2}+10n,{n}^{3},n\mathrm{log}n,{n}^{32}.$$ |

Problem 4.3 (Goodrich *et al* C-4.43 rephrased) Claim: *In any flock of sheep, all sheep
have the same colour*

An alleged proof goes as follows.

*Base Case:*
$n=1$
A single sheep clearly has the same colour as itself.

*Induction Step:* Consider a flock of
$n>1$
sheep. Take one sheep
$a$
out. The remaining
$n-1$
sheep have the same colour by induction. Now, replace
$a$
and take a different sheep
$b$
out. Again, the remaining
$n-1$
sheep have the same colour by induction. Hence, all the sheep in the flock have the same
colour.

In reality, we know that a flock with black and white sheep has been observed, so what is wrong with the argument?

##### 4.2.2 Compulsory Assignment

Problem 4.4 (Goodrich *et al* C-4.49 rephrased) Let
$p\left(x\right)$ be a
polynomial, i.e.

$$p\left(x\right)=\sum _{i=0}^{n}{a}_{i}{x}^{i}.$$ |

- 1.
- Describe an $O\left({n}^{2}\right)$-time algorithm to compute $p\left(x\right)$.
- 2.
- Improve the algorithm to $(n\mathrm{log}n)$ time by improving the calculation of ${x}^{i}$.
- 3.
- Now consider rewriting as
$$p\left(x\right)={a}_{0}+x({a}_{1}+x({a}_{2}+x({a}_{3}+\cdots +x({a}_{n-1}+x{a}_{n})\cdots \phantom{\rule{0.17em}{0ex}})\left)\right).$$ How many arithmetic operations do you need to calculate this (in Big-O notation).

Problem 4.5 (Goodrich *et al* R-4.31 rephrased) Al and Bob are arguing about their algorithms.
Al claims his $O(n\mathrm{log}n)$-time
algorithm is *always* faster than Bob’S $O\left({n}^{2}\right)$-time
algorithm. To settle the issue they run a set of experiments. To Al’s dismay, they find that if
$n<100$,
the $O\left({n}^{2}\right)$-algorithm
runs faster, and only when $n\ge 100$
is the $O(n\mathrm{log}n)$-time
one better. Explain how this is possible.

##### 4.2.3 Practice Problems

Problem 4.6 (Goodrich *et al* C-4.35 rephrased) Show that

$$\sum _{i=1}^{n}{i}^{2}=O\left({n}^{3}\right).$$ |

Problem 4.7 (Goodrich *et al* R-4.28 rephrased) Given an $n$-element
array $X$.
Algorithm A chooses $\mathrm{log}n$
elements from $X$
at random and executes an $O\left(n\right)$-time
calculation for each. What is the worst-cae running time of B.

Problem 4.8 (Goodrich *et al* R-4.30 rephrased) Given an $n$-element
array $X$.
Algorithm D calls Algorithm E on each element ${X}_{i}$.
Algorithm E runs in $O\left(i\right)$
time when called on ${X}_{i}$.
What is the worst-case run time of D?

Problem 4.9 (Goodrich *et al* P-4.55 rephrased) Make an experimental analysis to test the
hypothesis that Java’s Array.sort() method runs in
$O(n\cdot logn)$
time on average.

- 1.
- Proof techniques C-4.$x$