algorithm - 指数関数の Big O 表記法

Question

1000n または 10n の big-O は O(n) と同じものですが、2^n と 3^n の big-O は異なります: O(2^n) と O(3^n)、私が得られないのは、この場合の定数 (2 または 3) を無視できない理由と、これを正当化する数学的な証拠があるかどうかです。

Answer 1

任意に大きいkの不等式を満たすの定数値は存在しないためです。したがって、 は のメンバーではありません。3^n <= k * 2^nnf(n) = 3^nO(2^n)

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notationsを参照してください。