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[3]{10}$.

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

  • $\begingroup$ 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? $\endgroup$ May 28 '15 at 13:54
  • $\begingroup$ It doesn't affect the complexity of the algorithm if I understand correctly. $\endgroup$
    – Whitebird
    May 28 '15 at 13:57
  • $\begingroup$ I didn't say your answer was wrong. I'm trying to encourage you to find a justification. $\endgroup$ May 28 '15 at 14:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    May 28 '15 at 14:16
  • $\begingroup$ Thanks, do you have an alternative resource I could use? $\endgroup$
    – 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},$$

which gives the same answer you came up with!

  • $\begingroup$ Thank you, it seems that I came up with the same reasoning one way or the other. $\endgroup$
    – Whitebird
    May 28 '15 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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