0
$\begingroup$

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.

  • 0
    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.2012-05-10

1 Answers 1

2

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

  • 0
    Thanks so much. Now I understand.2012-05-10