# Express the following formula in terms of n

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.

-

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

-
This may be a dumb question, but if the equation had been $T(2^k)=\frac{k(k+1)}{2} +1.$ would the result be what you've written +1 ? – Bob John Feb 6 '13 at 4:18
@BobJohn: take a look at anorton's answer for more details. The answer is yes, if you add +1, then the result would be the same as what I wrote with a $+1$ as well. By saying $n=2^k$, you need to find how $k$ depends on $n$ and then plug that into every instance of $k$ in your equation. – Alex R. Feb 6 '13 at 4:21

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}$$

-