Expand recursive equation to convert it into a normal formula

Question

The Problem:

I am faced with the following recursive equation:

$$V(n) =\begin{cases} 2V(n/2)+n& \text{for n > 1}\\ 0 &\text{for n = 1} \end{cases}$$

I am trying to expand the function entirely and find a formula that is not recursive and is only dependent on n.

While I have proven by induction, that n log n works for that purpose, the expansion of the formula gives me a bit of trouble, since it doesn't seem even remotely related to n log n.

Question: How do I expand the recursive function above in a way, that clearly results in the formula n log n?

Here is what I have so far:

\begin{eqnarray*} V(n) &=& 2*V(n-1)+n\\ &=& 2*(2*V(n-2)+(n-1))+n\\ &=& 2*(2*(2*V(n-3)+(n-2))+(n-1))+n \\ &\vdots \\ &=& n\hspace{1mm} log\hspace{1mm} n \end{eqnarray*}

I appreciate any help given!

Answer 1

A: V(n) = 2 * V(n/2) + n

Replacing n by n/2 in equation A gives:

B: V(n/2) = 2 * V(n/(2^2)) + n/2

Replacing n by n/(2^2) in equation A gives:

C: V(n/(2^2)) = 2 * V(n/(2^3)) + n/(2^2)

Now, plugin the value of B in A

D: V(n) = 2 * [2 * V(n/(2^2)) + n/2] + n

Now, plugin the value of C in D

D: V(n) = 2 * [2 * [2 * V(n/(2^3)) + n/(2^2)] + n/2] + n

Simplifying

D: V(n) = 2^3 * V(n/(2^3)) + (2^2) * n / (2^2) + 2 * n / 2 + n

D: V(n) = 2^3 * V(n/(2^3)) + n + n + n

D: V(n) = 2^3 * V(n/(2^3)) + 3n

So the general form of the equation is:

V(n) = 2^k * V(n/(2^k)) + kn

We need to figure out what value of k will get is to the termination condition V(1)

n/(2^k) = 1

n = 2^k

k = log2 n

Substitute k in the general form of the equation gives:

V(n) = 2^(log2 n) * V(1) + (log2 n)n

Simplifying:

V(n) = n * V(1) + n (log2 n)

V(n) = n * 0 + n (log2 n)

V(n) = n (log2 n)

Answer 2

I think this belongs to Computer science, not to maths.

Have you heard of the Master-theorem? Try that, and you will see that the complexity is $O(n\log n)$.

Intuitively speaking, every time you have to divide your problem by 2 and add n steps (e.g. Quicksort, where you have to compare the pivot element with every other element). How many times do you have to divide? $\log n$, because you split the problem in 2. So you have $\log n$ steps, and on each step you have $O(n)$ steps, which makes time complexity of $O(n \log n)$. If you are not familiar with the Big-O notation, see this article.