已知f(n)=Θ(g(n))且f(n),g(n)≥2，求证log(f(n))是否等于Θ(log(g(n)))

前提约定（符合算法复杂度分析常规默认规则）：

1. 对数底数大于1；
2. $n$足够大时$g(n) > 1$，保证$\log(g(n))$为正；
3. $f(n) = \Theta(g(n))$即存在正整数$n_0$和正的常数$C_1、C_2$，对所有$n \geq n_0$，满足 C₁·g(n) ≤ f(n) ≤ C₂·g(n)

下界（$\Omega$）完整证明 #

我们需要找到正的常数$C_3$和$n_1 \geq n_0$，使得对所有$n \geq n_1$，满足 log(f(n)) ≥ C₃·log(g(n))。
从$\Theta$的定义对不等式两边取对数可得：
log(f(n)) ≥ log(C₁·g(n)) = log(C₁) + log(g(n))
接下来分两种情况讨论$C_1$的取值：

• 当$C_1 \geq 1$时：
  $\log(C_1) \geq 0$，直接代入可得 log(f(n)) ≥ 0 + log(g(n)) = 1·log(g(n))，此时取$C_3=1$，$n_1 = n_0$即可满足$\Omega$的定义。
• 当$0 < C_1 < 1$时：
  此时$\log(C_1)$为负数，记k = -log(C₁) > 0，不等式变形为 log(f(n)) ≥ log(g(n)) - k。
  结合$g(n)$的性质分两种子情况：
  1. 若$\log(g(n))$是有界正常数，即存在$M>0$使得$\log(g(n)) \leq M$对所有$n \geq n_0$成立。此时$\log(f(n)) \geq \log(C_1·g(n)) \geq \log(C_1·c)$（$c$为$g(n)$的下界，大于1）是固定常数，取C₃ = log(C₁·c)/M即可满足要求。
  2. 若$\log(g(n))$渐近趋于无穷，则必然存在$n_1 \geq n_0$，使得对所有$n \geq n_1$，有log(g(n)) ≥ 2k。代入不等式可得：
     log(f(n)) ≥ log(g(n)) - k ≥ log(g(n)) - log(g(n))/2 = (1/2)·log(g(n))
     此时取$C_3=1/2$即可满足$\Omega$的定义。

所有情况都能找到符合要求的固定常数，因此log(f(n)) = Ω(log(g(n)))得证。

上界（$O$）证明补充 #

你之前的推导完全成立，整理如下：
从$\Theta$的定义取上界对数得：
log(f(n)) ≤ log(C₂·g(n)) = log(C₂) + log(g(n))
由于$n$足够大时$\log(g(n))>1$，因此log(C₂) ≤ log(C₂)·log(g(n))，代入得：
log(f(n)) ≤ log(C₂)·log(g(n)) + log(g(n)) = (log(C₂)+1)·log(g(n))
取$C_4 = \log(C_2)+1$，$n_1 = n_0$即可满足$O$的定义，因此log(f(n)) = O(log(g(n)))。

最终结论 #

结合上下界证明可得：在常规复杂度分析前提下，若f(n) = Θ(g(n))，则log(f(n)) = Θ(log(g(n)))，你要证明的$\Omega$关系自然成立。

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