# Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster

I am trying to solve the following question

There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose there's another computer which is 10 times faster. How much bigger can our $n$ be to be solved in the same time?

My answer so far is $\sqrt{10}$.

$n^3$ can be 10 times bigger, so I have to multiply N with $\sqrt{10}$. Is my conclusion correct or is there a fault in my reasoning?

• Hint: the increase in speed this new computer brings is not a function of $n$, so how would it affect the complexity of the algorithm? – André Souza Lemos May 28 '15 at 13:54
• It doesn't affect the complexity of the algorithm if I understand correctly. – Whitebird May 28 '15 at 13:57
• I didn't say your answer was wrong. I'm trying to encourage you to find a justification. – André Souza Lemos May 28 '15 at 14:03
• Welcome to SE Computer Science. We cannot answer you, because the answer YES is too short, thus not accepted by the system. So questions with yes/no answers, or check whether my answer is correct, are often not considered useful, actually because the do not lead to interesting developments. Presentation matters a lot on SE :) Well... I managed to do it in more than one word. – babou May 28 '15 at 14:16
• Thanks, do you have an alternative resource I could use? – Whitebird May 28 '15 at 14:47

You've correctly reasoned that the additional speed doesn't change the $n^3$ part of the tilde expression. The only component left for it to effect then is $c$.
Let $c_1$ be the constant of the first computer and $c_2$ the constant of the second. If the second computer is 10x faster, then $c_2 = c_1/10.$ Now, all you need to do is solve the following equation:
$$c_1 \cdot n^3 = \frac{c_1 \cdot n'^3}{10},$$