# Computational complexity based in the input size

In an answer to a previous question Luke Mathieson wrote:

A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n=O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^n)$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

Can you explain to me how if the running time is $O(m)$ goes to $O(2^n)$?

• Sorry, I thought this would be a private message, but feel free to answer. Thank you! Jul 14 '15 at 1:34
• There's no private message system on Stack Exchange. Jul 14 '15 at 1:37

Let the length of the input (in bits) be $n$ and let the number represented be $m$. We have $n \approx \log_2 m$ (that's how many bits it takes to write down the number $m$) so $m\approx 2^n$.