Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 9 down vote accepted

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$

share|improve this answer
add comment

Suppose that the complexity is $n^2$; then the time $t_1(n)$ required to solve a problem of size $n$ is $t_1(n)=an^2$ for some positive proportionality constant $a$. Now suppose that you make the machine run twice as fast; that cuts the required time in half, so the new required time is $t_2(n)=\frac12an^2$.

Now suppose that the original machine can solve a problem of size $n_0$ in $1$ hour, so that $$t_1(n_0)=an_0^2=1\;;$$ clearly $a=\dfrac1{n_0^2}$. Then the faster machine takes

$$t_2(n)=\frac12an^2=\frac1{2n_0^2}n^2\tag{1}$$

hours to solve a problem of size $n$. To see what the improvement is, use $(1)$ to find out how big a problem the faster machine can solve in one hour by solving the equation

$$\frac1{2n_0^2}n^2=1\tag{2}$$

to get $$n=\sqrt{2n_0^2}=\sqrt2~n_0\;.$$ In other words, the faster machine can solve in one hour a problem that is bigger by a factor of $\sqrt 2$ than the largest problem that the slower machine can solve in one hour. The same proportion holds for any other time period.

Similar analyses will yield the other results that you mention.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.