The order of a particular algorithm...Please help!

anthmoo · #1 $Old$ January 14th, 2007, 06:55 AM

The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

thanks guys!

CaptainBlack · #2 $Old$ January 14th, 2007, 07:42 AM

Quote:

Originally Posted by anthmoo $View Post$

The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

thanks guys!

$T(n)=O(n^3)$

So there exists a $k$ such that; if $n$ is large enough:

$T(n)\approx k\,n^3$

so if $T(100)= 4\ s$ , $k\approx 4/10^6$ and:

$T(500)\approx (4/10^6) 5^3 10^6=500\ s$

RonL