Обозначение Little-oh для двух логарифмических функций?

У меня есть следующая функция (с естественным логарифмом и логарифмической базой 2):

и я пытаюсь доказать справедливость этого утверждения. Я верю, что это правда. Все логарифмы асимптотически эквивалентны друг другу. Я пытаюсь написать формальное доказательство этого и найти и это сделало бы мой аргумент верным. Я использую маленькое определение:

0 =< f(n) < g(n)

0 =< lg(n) < ln(n^2)

0 =< lg(n) < 2 ln(n)

Это примерно то, что я получил, но у меня возникли проблемы с завершением доказательства и поиском значений c и n_0. Может ли кто-нибудь помочь мне с этим?


runtime time-complexity complexity-theory proof little-o
person greendaysbomb    schedule 22.11.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Неправда, что log_2(n) ∈ o(ln(n^2)). Чтобы непосредственно увидеть это, вы можете рассмотреть предел log_2(n)/ln(n^2), поскольку n стремится к бесконечности, что соответствует 2/ln(2) ∈ (0, ∞). Таким образом, log_2(n) ∈ Θ(ln(n^2)).
Это означает, что вы можете найти две константы c₁ и c₂ и размер ввода n₀ такой, что c₁⋅log_2(n) ≤ ln(n^2) ≤ c₂⋅log_2(n) для всех n ≥ n₀

person abc    schedule 22.11.2020