algorithm - Time spent to sort 10^7 records with insertion sort -

algorithm - Time spent to sort 10^7 records with insertion sort -

i stuck revision upcoming test.

the question says:

an implementation of insertion sort spent 1 sec sort list of 10^6 records. how many seconds spend sort 10^7 records?

by using

t(x)/t(1) = 10^7/10^6

i thought reply 10 seconds actual reply says it's 100 seconds.

can please help me out?

your reply have been right if insertion sort operation ran in linear (i.e. o(n)) time. it's not.

insertion sort has average-case complexity of o(n^2) (i.e. it's quadratic). loosely, means on average take 4 times long sort 2 times many records; 9 times long sort 3 times many; 16 times long sort 4 times many; , forth.

the question asks how long take sort 10 times many records; what's 10 squared times 1 second?

algorithm time-complexity insertion-sort