If an algorithm runs in time $f(n)$, according to the recursion: $$f(n) = nf(n/2).$$where $f(1)=1$. How do I find an expression for $f(n)$ in terms of $n$ (supposing I assume $n$ is a power of 2) ?
My solution: Given, $f(n) = nf\left( \frac{n}{2}\right) = 1$.\ Suppose $\mathbf{n}$ is a power of 2 i.e $n=2^k$ for some positive integer k.\ Therefore, \begin{align} f(n) &= nf\left( \frac{n}{2}\right) \nonumber \\ &= n\cdot \frac{n}{2} \cdot f\left(\frac{n}{2^2}\right) \nonumber \\ &= n\cdot \frac{n}{2} \cdot \frac{n}{2^2} \cdot f\left( \frac{n}{2^3}\right) \nonumber \\ \Rightarrow{} f(n) &= n\cdot \frac{n}{2} \cdot \frac{n}{2^2} \cdot\cdot\cdot \frac{n}{2^{k-1}} \cdot f\left( \frac{n}{2^k}\right) \nonumber \\ \Rightarrow{} f(n) &= n\cdot \frac{n}{2} \cdot \frac{n}{2^2} \cdot\cdot\cdot \frac{n}{2^{k-1}} \cdot f\left( \frac{2^k}{2^k}\right) \quad \mathbf{since \quad n = 2^k} \nonumber \\ \Rightarrow{} f(n) &= n\cdot \frac{n}{2} \cdot \frac{n}{2^2} \cdot\cdot\cdot \frac{n}{2^{k-1}} \cdot f(1) \nonumber \\ &= n \nonumber \\ \Rightarrow{} f(n) &= n\cdot \frac{n}{2} \cdot \frac{n}{2^2} \cdot\cdot\cdot \frac{n}{2^{k-1}} \cdot 1 \nonumber \\ \Rightarrow{} f(n) &= \frac{n^k}{2\cdot 2^2 \cdot 2^3 \cdot\cdot\cdot 2^{k-1}} \nonumber \\ &= \frac{n^k}{2^{\frac{k(k-1)}{2}}} \nonumber \end{align} Thus, the expression for $f(n)$ in terms of $n$ is: $$f(n) = \frac{n^k}{2^{\frac{k(k-1)}{2}}}$$
How can I simplify my final expression further so that it does not include k?