Express the following formula in terms of n

Question

Express $$ T(2^k)=\frac{k(k+1)}{2}. $$

In terms of $n$, where $n = 2^k$.

I'm not sure how to go about with the conversion. Can someone concisely explain?

Thank you.

Answer 1

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

Answer 2

Alex's answer is correct; I thought I'd work the problem in "slow motion:"

$$n=2^k$$ We have an exponential. We want to solve for $k$, which essentially begs for a $\log$ function. $\log_2$ is an ideal choice, as it cancels out the $2^k$ in the definition of $T$.

So, taking the $\log_2$ of both sides: $$\log_2 n = \log_2(2^k)$$ $$\log_2 n = k\log_2(2)$$ $$\log_2 n = k$$

Substituting: $$T(2^k) = \frac{k(k+1)}{2}$$ $$T(2^{\log_2 n}) = \frac{\left(\log_2{n}\right)(\log_2 n+1)}{2}$$ Simplify: $$T(n) = \frac{\left(\log_2{n}\right)(\log_2 n+1)}{2}$$