Time spent to sort $10^7$ records with insertion sort

59 Views Asked by At

I am stuck with my revision for the upcoming test.

The question asks"

An implementation of insertion sort spent 1 second to sort a list of ${10^6}$ records. How many seconds it will spend to sort ${10^7}$ records?

By using $\frac{T(x)}{T(1)}$ = $\frac{10^7}{10^6}$ I thought the answer was $10$ seconds but the actual answer says it's $100$ seconds.

Can someone please help me out? :(

2

There are 2 best solutions below

0
On BEST ANSWER

Hint: Time complexity of Insertion sort is $O(n^2)$

Roughly speaking if $10^6$ records took $1$ second then

$10\times 10^6$ records will take $10^2\times1=100$ seconds

0
On

Hint: what is the Time Complexity of insertion sort?