Big O if 2^n vs. 4^n

Question

我想弄清楚这两个大O。显然，大O(2^n)是O(2^n)但我不确定你能不能简化4^n。如果是这样，我就用4^n = (2^2)^n。然后我们可以把它分配成2^(2n)我把它化简成O(2^n)因为n前面的常数不重要。

正确吗?谢谢你。

Answer 1

让我们试着自己得出这个结论。假设4^n = 0 (2^n)然后存在某个m和某个c，使得对于所有n>= m的4^n <= c*2^n，然后我们有对于所有n>= m的

   (2*2)^n <= c*2^n
=> 2^n * 2^n <= c*2^n
=> c >= 2^n

所以c显然不是常数，这是一个矛盾

Answer 2

来自维基百科上的大O:

另一方面，不同基底的指数不属于同一阶。例如，2^n和3^n不是同一阶。