Problem Detail: Say I have some problem of $Oleft(n^kright)$ complexity. If I were to solve the problem on a computer $x$, it would take time $t$. Now I have a new computer $x’$, which has double the computing power of $x$. How long would it take $x’$ to solve the same problem in terms of $t$?
Asked By : JibbyJames
Answered By : Yves Daoust
It will take half the time of course, $t’=t/2$, and the asymptotic complexity remains $O(n^k)$ !
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40558 Ask a Question Download Related Notes/Documents
