algorithm - big-o表記での指数関数的成長

Question

次の質問を理解するのに問題があります。それは言います：

指数関数は、底の値が異なると成長の次数が異なることを証明してください。

たとえば、 a ⁿを考えてみましょう。a=3 の場合、a=2 の場合よりも成長率が大きくなります。それは明らかです。それは本当に質問が望んでいることですか？それを正式に証明するにはどうすればよいですか？

よろしくお願いします。

Answer 1

f(n) ∈ O(g(n)) は、すべての n ≥ k に対して 0 ≤ f(n) ≤ cg(n) となる正の定数 c と k があることを意味します。関数 f の c と k の値は固定である必要があり、n に依存してはなりません。

一般性を失うことなく 1>a>b とし、b^n ∈ O(a^n) とします。これは、すべての n ≥ k に対して 0 ≤ b^n ≤ ca^n となるような正の定数 c および k が存在することを意味します。これは不可能です: すべての n ≥ k に対して
b^n ≤ ca^n は (b/a)^すべての n ≥ k に対して n ≤ c で
あり、b/a>1 であるため、lim (b/a)^n = +inf と矛盾します。

1>a>b なら b^n ∉ O(a^n) ですが、a^n ∈ O(b^n) なので O(a^n)⊊O(b^n)