CODEWITHSUNDEEP
sortingbig-omergesortinsertion-sort
Jim Lindberg
Jim Lindberg

Reputation: 33

Time for insertion sort vs mergesort

If insertion sort and mergesort takes the same amount of time for 1000 elements, say 1 second, how long would it take for each algorithm to sort 10^6 elements and 10^9 elements respectively?

Big O for insertion sort and mergesort is n^2 and n*log n respectively.

This is actually a side question on an assignment I have so there should be a solid answer.

Please explain the rationale behind your answer.

Upvotes: 0

Views: 1776

Answers (2)

Zhuoran He
Zhuoran He

Reputation: 973

The time complexity of insersion sort is O(n^2), so the time scales quadratically with the number n of elements to sort. If n=1000 takes 1 second, then n=10^6 takes 1*(10^6/1000)^2=10^6 seconds, and n=10^9 takes 1*(10^9/1000)^2=10^12 seconds. Mergesort time complexity is O(n*log(n)). So the times can be scaled accordingly to find that n=10^6 takes 2000 seconds and n=10^9 takes 3*10^6 seconds. Since both O(n^2) and O(n*log(n)) are higher than O(n), we can ignore, let's say, the time needed to allocate the extra storage space O(n) for merge sort in the large n limit and estimate based solely on the sorting time complexity. Hope this helps.

Upvotes: 0

D-Von
D-Von

Reputation: 426

My answer is that the question cannot be answered, since we aren't told anything about the element size and the manner in which mergesort will acquire the working memory it needs. (Insertion sort requires constant additional memory; mergesort requires O(n) additional memory.) If elements are 100KiB, then allocating the working memory will take significant time.

Upvotes: 1

Related Questions