How to solve this type of recursive formula?

Question

I know how to solve recursive formulas when the T(n) term is a whole number. However, when it isn't, I have no idea what to do. Can someone explain this to me with regards to solving this problem?

    Solve the following recursive formula.
    Try to find the exact solution. If you cannot use, Big Oh, Omega or Theta notations.

 n>=1 is a power of 2 integer.
 T(1)=0
 T(n)=2T(n/2)+n

I have tried the following thus far.

I know that

T(2) = 2T(1) + 2 =2 
T(4) = 2T(2) + 4 =8

However, I don't know what to do about

T(3) = 2T(3/2) + 3

I don't understand how you can have a 1.5th term T(3/2). Can someone please help me to understand and solve this? Thanks

Answer 1

we get $$T(n)=T \left( 1 \right) n+{\frac {n\ln \left( n \right) }{\ln \left( 2 \right) }} $$ for all $n \in \mathbb{N}$

Answer 2

This recursion is of the form $T(n) = aT\left(\frac nb\right) + f(n)$ where $f(n)\in\Theta\left(n^{\log_b a} \log^0 n \right)$, so by the master theorem, we have $T(n)\in\Theta(n\log n)$. When $n=2^k$, $k=0,1,2,\ldots$ we may verify by induction that this is an exact solution to the recurrence. That is, $T\left(2^k\right) = k2^k$ for $k\geqslant 0$. The base case $k=0$ is trivial, as $$0 = T\left(2^0\right) = 0\cdot 2^0. $$ Assume that $T\left(2^k\right)=k2^k$ for some nonnegative integer $k$. Then \begin{align} T\left(2^{k+1}\right) &= 2T\left(2^k\right) + 2^{k+1}\\ &= 2\left(k2^k\right) + 2^{k+1}\\ &= (k+1)2^{k+1}, \end{align} from which we conclude.

Answer 3

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\mrm{T}\pars{1} = 0\,,\quad \mrm{T}\pars{n} = 2\,\mrm{T}\pars{n/2} + n:\ ?\,;\qquad n \equiv 2^{\ell}\,,\ \ell \geq 0.\quad\mbox{Note that}\ \ell = \ln\pars{n}/\ln\pars{2}}$.

\begin{align} \mrm{T}\pars{n} = 2\,\mrm{T}\pars{n \over 2} + n \implies {\mrm{T}\pars{n} \over n} & = {\mrm{T}\pars{n/2} \over n/2} + 1 = {\mrm{T}\pars{n/2^{2}} \over n/2^{2}} + 2 = {\mrm{T}\pars{n/2^{3}} \over n/2^{3}} + 3 \\[5mm] & = \cdots = {\mrm{T}\pars{n/2^{\ell}} \over n/2^{\ell}} + \ell\ =\ \overbrace{\mrm{T}\pars{1}}^{\ds{=\ 0}}\ +\ \ell = {\ln\pars{n} \over \ln\pars{2}} \\[5mm] &\implies\quad \bbox[8px,border:0.1em groove navy]{\mrm{T}\pars{n} = {n\ln\pars{n} \over \ln\pars{2}}} \end{align}