algorithm - log(n-f(n)) 是 log(n) 的大 theta

Question

问题是我需要知道 log(n-f(n)) 是否是 log(n) 的大 theta，其中 f(n) 是比 n 低阶的函数，例如 log(n) 或 sqrt(n)。

我尝试使用一些日志规则，绘图似乎可以确认界限，但我无法准确理解。

Answer 1

作为f(n)是比 n 低阶的函数, f(n) = o(n) .因此，n-o(n) < 2n和 n - o(n) = O(n) .另外，n - o(n) > n - 0.01 n <=> 0.01 n > o(n) ( 0.01 可以用 o(n) 指定)。因此，n - o(n) = Omega(n) , 和 n-o(n) = Theta(n) .

作为log函数是一个递增函数，我们可以说 log(n-o(n)) = Theta(log(n)) .