algorithm - 大 O 如果 2^n 与 4^n

Question

我正在尝试找出这两个大 O。很明显2^n的大O是O(2^n)，但是我不确定你能不能减少4^n。如果是这样，我会做 4^n = (2^2)^n。然后我们可以分配使这个 2^(2n)，我会减少到 O(2^n) 因为 n 前面的常量无关紧要。

这是正确的吗？谢谢。

Answer 1

让我们尝试自己解决这个问题。假设 4^n = O(2^n)。然后有一些 m 和一些 c，使得 4^n <= c*2^n 对于所有 n >= m。那么对于所有 n >= m:

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

所以c显然不能是常量，矛盾。