在大O表示法中，为什么8^n是O(2^n)的？

Question

我不知道为什么8^n的复杂度是2^n，更具体地说，问题是如何求出1/3*8^n-10的复杂性。

Answer 1

我将试图给出关于如何证明你的陈述是错误的粗略的指导方针。

假设你是对的

$8^n = O(2^n) $，根据定义，存在N(自然数)和M(常数实数，大于0)，使得对于所有n> N：

$ 8^n

由此可以得出$M> (8^n)/(2^n) = (8/2)^n = 4^n$的结论。

由于M是常数，所以8^n不是O(2^n)。

您也可以使用lim sup定义来显示它。