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

Question

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.

Answer 1

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