Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A algorithm require one second to resolve a problem of size $1000$ a local machine.

How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm require a proportional time to $n^2$?

I think that:

T(1000) = 1 second, but I don't know how to establish relationship with $n^2$


share|cite|improve this question
isn't it just time required $=k\times n^2$ where n is the problem size.. Where $k$ is some constant – picakhu May 10 '12 at 14:47
$T\propto n^2$. As there are no other variables assume $T=\alpha n^2$ and use this one data point you have $T(1000)=1s$ to determin $\alpha$. – example May 10 '12 at 14:47
Suppose time taken is proportional to $n^2$. Then if you double the size of the problem, time gets multiplied by $2^2$. If you triple the size, time gets multiplied by $3^2$. If you multiply size by $10$, then time gets multiplied by $10^2$. And so on. – André Nicolas May 10 '12 at 16:01
up vote 2 down vote accepted

The algorithm requiring time proportional to $n^2$, where $n$ is the size of the input, means $T(n)=Cn^2$, where $C$ is the constant of proportionality. Since you're given that $C \cdot 1,000^{2} = T(1,000)=1$, we can conclude that $C=1000^{-2}$. Thus $T(10,000) = 1000^{-2} \cdot 10,000^2 = 100$.

share|cite|improve this answer
Thanks so much. Now I understand. – Albert May 10 '12 at 15:04

Your Answer


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.