Recurrence relation simplification

Question

I have initial condition $n_1=2, v_1=1$, and the given recurrence relations: $n_{i+1}=2n_i,$ $v_{i+1}=2v_i+\frac{1}{2} n_i$ I need to show that that, $v_i=\Theta(n_i\log⁡ n_i).$

I observe that $n_i=2^i$, how to proceed from here.

Answer 1

As you already stated, first we conclude that the solution of the recurrence $n_{i+1} = 2n_i$ with $n_1 = 2$ is indeed $n_i = 2^i$.

So the recurrence $v_{i+1} = 2v_i + \frac{1}{2}n_i$ now becomes $v_{i+1} = 2v_i + \frac{1}{2}2^i = 2v_i + 2^{i-1}$.

\begin{align} v_{i+1} &= 2v_i + \frac{1}{2}n_i \\ &=2\left[2v_{i-1} + \frac{1}{2}n_{i-1}\right] + \frac{1}{2}n_i \\ &= 2^2v_{i-1} + \frac{1}{2}[n_i + 2n_{i-1}] \\ &= 2^2v_{i-1} + \frac{1}{2}\times 2n_i \tag{using $n_{i} = 2n_{i-1}$}\\ &= 2^2\left[2v_{i-2} + \frac{1}{2}n_{i-2}\right] + \frac{1}{2}\times 2n_i \\ &= 2^3v_{i-2} + \frac{1}{2}\times 3n_i \\ \vdots\\ &= 2^kv_{i-k+1} + \frac{1}{2}\times kn_i \end{align} Now, by setting $k=i$ and using $n_i = 2^i$, we get \begin{align} v_{i+1} &= 2^iv_1 + \frac{1}{2}\times i\times n_i \\ &= n_i\times 1 + \frac{1}{2}\times \log n_i\times n_i \end{align} Thus, $v_i = \Theta(n_i\log n_i) = \Theta(2^i \cdot i)$.