$T(n) = nT(n/2) ,T(1)=1$ How can I solve this with backward subsitituon?

Question

$n$ can be power of 2 or we can assume $Integerpart(n/2)$ ==> int casting.

I find the recurrence relation of function but How can I solve this with using backward subsitituon ?

My recurrence relation solution

Answer 1

As pointed out in my comment, you can use the next hint:

Observe that $S(k) = 2^k S(k-1)$ and the fact that we know the value of $S(0)$. Next use backward substitution to "unroll" $S(k)$ until you get to $S(0)$ on the RHS. Using your "unrolled" expression for $S(k)$ you should be able to find $T(n)$

:)

Answer 2

Notice that the expression $T(n)$ starts with $n$ so in general you have

$$T(n)=n\frac{n}{2}\frac{n}{4}...\frac{n}{2^k}...1$$

Obviously the last $1$ is in the same format so it must be

$$\frac{n}{2^M}=1$$

or

$$n=2^M$$

From there it is obvious that we have $M+1$ terms in form of

$$\frac{n}{2^k}=1$$

where $M$ is $\log_2(n)$

We can write then

$$T(n)=\frac{n^{M+1}}{ 2^{ \frac{M(M+1)} {2} } }$$

or precisely after the substitution of $M$

$$T(n)=n^{\log_4(2n)}$$

Answer 3

$$ T\left(2^{\log_2 n}\right) = n T\left(2^{\log_2 \frac n2}\right) $$

now calling

$$ \cases{ \mathcal{T}\left(\cdot\right) = T\left(2^{(\cdot)}\right)\\ z = \log_2 n } $$

we have the equivalent recurrence

$$ \mathcal{T}\left(z\right)=2^z \mathcal{T}\left(z-1\right) $$

This recurrence has as solution

$$ \mathcal{T}\left(z\right) = c_0 2^z\cdot 2^{z-1}\cdot 2^{z-2}\cdots 1 = c_0 2^{\frac{z(z+1)}{2}} $$

now with the backwards substitution $z = \log_2 n$ we recover

$$ T(n) = c_02^{\frac{(\log_2 n)^2+\log_2 n}{2}} = c_02^{\frac{(\log_2 n)^2}{2}}\sqrt{n} $$

and due to the initial condition

$$ T(n) = 2^{\frac{(\log_2 n)^2}{2}}\sqrt{n}=n^{\frac{1+\log_2 n}{2}} $$