Доказать или опровергнуть n 〖log〗 _10 n ∈θ (n 〖log〗 _2 n)

Question

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

Answer 1

Основная идея, которую нужно иметь в виду, заключается в следующем:

(log_a x)(log_2 a) = (log_2 x)

Почему?Потому что

(log_a x)(log_2 a) = log_2 a^(log_a x)        ; t(log_2 a) = log_2 a^t
                   = log_2 x                  ; a^(log_a x) = x by definition

Для a=10 и x=n получаем:

(log_10 n) = (log_2 n)/(log_2 10)

, умножим на n:

n(log_10 n) = n(log_2 n)/(log_2 10)

и получим

n(log_10 n) = θ(n(log_2 n))

, поскольку log_2 10 является константой.

Answer 2

Вернитесь на шаг и посмотрите, как база журналов влияет на сложность.Если вы можете показать, что сложность log10 такая же, как log2, вы окажетесь на правильном пути