### Exercise

#### 2.17

Solve the recurrence $A_{N}=A_{N-1}-\frac{2 A_{N-1}}{N}+2\left(1-\frac{2 A_{N-1}}{N}\right) \quad \text { for } N>0 \text { with } A_{0}=0$.

This recurrence describes the following random process: A set of $N$ elements collect into “2-nodes” and “3-nodes.” At each step each 2-node is likely to turn into a 3-node with probability $2/N$ and each 3-node is likely to turn into two 2-nodes with probability $3/N$ What is the average number of 2-nodes after $N$ steps?

#### 2.69

Plot the periodic part of the solution to the recurrence $a_{N}=3 a_{\lfloor N / 3\rfloor}+N \quad \text { for } N>3 \text { with } a_{1}=a_{2}=a_{3}=1$ for $1 \leq N \leq 972$.

### Problem

#### 1

Suppose that $a_{n}=2 a_{\lfloor n / 3\rfloor} + n \text { for } n>2 \text { with } a_{0}=a_{1}=a_{2}=1$. What is the order of growth of $a_n$?

• $\Theta\left(n^{3}\right)$
• $\Theta\left(n^{2}\right)$
• $\Theta(n \log n)$
• $\Theta(n)$

#### 2

Which of the following is true of the number of comparisons used by Mergesort?

• Has periodic behavior
• Order of growth is $N \lg N$
• Exactly $N \lg N$ when $N$ is a power of $2$
• Is less than $N \lg N + N/4$ for all $N$

#### 3

Suppose that $n a_{n}=(n-3) a_{n-1}+n$ for $n>2$ with $a_{0}=a_{1}=a_{2}=0$. What is the value of $a_{999}$?