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)$?
Let the length of the input (in bits) be $n$ and let the number represented be&nbsp;$m$.  We have $n \approx \log_2 m$ (that's how many bits it takes to write down the number&nbsp;$m$) so $m\approx 2^n$.