有没有简便方法证明2^(log n) = Ω(n)？（log底数为2）

首先明确两个前置基础：

• 对数恒等式：当对数底数为2时，对任意正整数n，2^(log₂n) = n 恒成立，这是对数与指数运算互逆的直接结论
• 大Ω记号的定义：函数f(n) = Ω(g(n)) 等价于存在正实数c、正整数n₀，使得所有n ≥ n₀时，满足 f(n) ≥ c·g(n)

直接证明步骤 #

你要证的式子完全不需要推导复杂不等式，直接代入定义即可：

1. 由对数恒等式得f(n) = 2^(log₂n) = n
2. 取常数c=1，n₀=1
3. 对所有n ≥ 1，都有 n ≥ 1·n 恒成立，完全满足大Ω的要求
   因此可直接得出 2^(log₂n) = Ω(n) 成立，这是最简便的证明方法。

之前思路出错的原因 #

你尝试推导n^(1/4) ≤ log n的方向完全走偏了，大概率是把要证明的原式记错了：如果是要证明类似2^{√(log₂n)} = Ω(n^k)（指数为对数的幂次形式）这类问题，才需要两边取对数后推导不等式。如果确实是你提问里给出的原式，用上述对数恒等式直接代入即可完成证明。

内容的提问来源于stack exchange，提问作者Jin