вопрос относительно асимптотического поведения во время выполнения

Question

Мы знаем, что log(n) = O(sqrt n). Мне интересно, можно ли сказать, что log(n) - это theta( sqrt n) . численно я доказал, что это правильно; но я не уверен в этом. Нужна помощь

Answer 1

log n НЕ в Theta(sqrt n), поскольку sqrt n асимптотически больше, чем log n, означающий, что log n не в Omega(sqrt n). Другими словами,sqrt n не может быть асимптотической нижней оценкой для log n.

Обратитесь к этому определению большой теты. Заменаsqrt n за g(n) а также log n за f(n) в определении, и вы увидите, что легко найдете k2 а также n0 такое, что определение удовлетворяется (вот почему log n в O(sqrt n)), при поиске подходящего k1 окажется невозможным (вот почему log n НЕ в Omega(sqrt n)).