Time complexity - Why does doubling the speed given this improvement? Hi I've been studying time complexity recently and I'm really confused about something I've come across. **The problem** _Suppose we can solve a size n problem instance in 1 hour. If we double the machine speed, how big a problem instance can we now solve?_ **The Answer** Complexity: $log_2(n)$ Improvement: $n \rightarrow n^2$ Complexity: $n$ Improvement: $n \rightarrow 2n$ Complexity: $n^2$ Improvement: $n \rightarrow \sqrt{2}n$ Complexity: $2^n$ Improvement: $n \rightarrow n+1$ **The Question** I understand the improvement for complexity $n$. Doubling the machine speed gives you $2n$, but what I fail to see is why for the other complexities we get that particular improvement! e.g. Why does doubling the machine speed for complexity $n^2$ give us an improvement of $\sqrt{2}n$. Could someone please explain what I'm missing. Thank you.

This is the point of the complexity measure. If the machine speed doubles, you can afford twice as many operations. If you have a process of complexity $n^2$ , you ask what $m$ will give twice as many operations. So we want $m^2=2n^2$ and solve it to get $m=\sqrt 2 n$. Similarly for a process with complexity $\log_2 n$, we ask what $m$ would give us $\log_2m = 2 \log_2 n$ By the laws of logarithms, this is solved by $m=n^2$