Является ли log (nf (n)) большим тэта log (n)

Question

Проблема в том, что мне нужно знать, является ли log(n-f(n)) большим тэта log(n), где 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)). Therfore, n - o(n) = Omega(n) и n-o(n) = Theta(n).

Поскольку log функция является возрастающей функцией, мы можем сказать log(n-o(n)) = Theta(log(n)).