大O如果2 ^ n对4 ^ n

Question

我想弄清楚这两个Big O's.显然2 ^ n的大O是O(2 ^ n),但我不确定你是否可以减少4 ^ n.如果是这样,我会做4 ^ n =(2 ^ 2)^ n.然后我们可以分配这个2 ^(2n),我会减少到O(2 ^ n),因为n前面的常数无关紧要.

它是否正确？谢谢.

Answer 1

来自Big O的维基百科:

另一方面,具有不同碱基的指数不是相同的顺序.例如,2 ^ n和3 ^ n的顺序不同.

Answer 2

让我们试着为自己做到这一点.假设4 ^ n = O(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显然不是恒定的,矛盾的.