Блог

Проблема в том, что мне нужно знать, является ли log(n-f(n)) большая тета для log(n) , где f(n) функция более низкого порядка, чем n , например, log(n) или sqrt(n) .

Я попытался использовать некоторые правила ведения журнала, и построение графика, похоже, подтверждает границу, но я не могу получить ее точно.

As 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)) .