基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

O(n^2) と O(n log_2 n)の平均実行時間の差が1/10であるとなっている。
素直に計算すると、O(n^2)=10^6, O(n log_2 n)≒10^4となる。10^4/10^6=1/100となり, 問題文よりも差が1/10小さい事になる。
このことからn=1,000,000の場合, 素直に計算するとO(n^2)=10^12, O(n log_2 n)≒20*10^6となり, 差は1/50,000となる。
しかし, この値は1/10小さい値の為, 10倍する必要がある, よって答えが「1/5000」になるという解釈で良いのでしょうか？

その解釈で合ってると思います…自信はないけど

n=1,000の時の比率は1/100で「差は1/10だった」という事は
比率×10  で差が出るということ

n=1,000,000の時の比率は1/50,000なので
比率×10  で差を出すと1/5,000になりますね

でも何か見落としてるような気がして不安が残ります

１計算量あたりの実行時間が、QとIで違うってことなんでしょうね。

計算量は1/100なのに実行時間は1/10ということは、
Qの１計算あたりの実行時間は、Iの１計算あたりの実行時間の10倍。

n=1,000,000になると計算量は1/50,000
実行時間で見ると、10倍しないといけないから1/5,000

まず, 「計算量≠平均実行時間」という理解が足りませんでした.

≪私の解釈≫
まず, 計算量と平均実行時間の関係を考える.
n=1,000の時に, 計算量の比が「I:Q=100:1」, 平均実行時間の比が「I:Q=10:1」という関係を得ることができ, 計算量と平均実行時間の比が「計:実=1/100:1/10」→「計:実=1:10」となる.（これを①とする）

これを使ってn=1,000,000の場合の計算量と平均実行時間の比率を解くことができる .

n=1,000,000の時, 計算量の比は, 「I:Q=50,000:1」, ①の関係より
「1/50,000:実=1:10」となりこれを解くと,
平均実行時間は「1/5,000」となる.

と解釈しました.
回答していただきありがとうございました.

一晩寝て、もう少し頭が整理できました:-)
計算量という表現が紛らわしいですが、そもそもO(…)という書き方なので、計算量そのものというより、計算量がnにどう依存するかを示しているだけ。

nに依存して増える計算量というのは、要するに繰り返し回数ですね。
しかし、そもそも繰り返している内容がアルゴリズムによって異なるので、繰り返し回数が1/100だから100倍速く処理が済むとは限らない。
そして実際、この問題の例では10倍にしかならなかった。
そこも含めて処理時間を求めてね、という話。