$T(n) = nT(n/2) ,T(1)=1$ How can I solve this with backward subsitituon? $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
 A: $$
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}}
$$
A: 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)$
:)
A: 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)}$$
