H19  春  午後問４の、設問３のやり方がイマイチよくわかりません・・・
外のサイトにも解説が無いようなので、教えてほしいです。

この頃の問題はとても難しく、最近ではまず出ないでしょうが、チャレンジし甲斐があります。

1,000個のデータの整列時間は、InsertSortが10に対して、QuickSortが1です。1,000,000個のデータの整列時間が、1,000個の場合に比べて何倍になるかを求めます。

InsertSort
n^2に比例するため、1,000,000^2／1,000^2倍です。
これを計算すると、10^12／10^6＝10^6倍となり、1,000個の場合の時間が10ですから、10^7です。

QuickSort
n log2 nに比例するため、1,000,000×log2 1,000,000／(1,000×log2 1,000)倍です。
これを計算すると、10^6×20／(10^3×10)＝2×10^3倍となり、1,000個の場合の時間が1ですから、2×10^3です。

QuickSortの時間／InsertSortの時間＝2×10^3／10^7＝2／10^4＝1／5,000
よって、正解は5,000(ウ)