Answer to Question #99849 in Algorithms for Steve

Question

You are running algorithm with squared complexity on data with 100 elements and it takes 10 seconds. How much time do you expect the algorithm will take when executed on data with 1000 elements?

Answer 1

Calculate the ratio of the increased number of elements with regard to the 100 elements:

$$n=1000/100=10.$$

An algorithm with squared complexity will require time

$$m=n^2=10^2=100$$

times longer than the time for 100 elements, i.e.

$$t_2=mt_1=100\cdot10=1000\text{ s},$$

or 16 minutes 40 seconds.