# Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?

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$

Thanks.

-
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

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$.