Я выбрал правильный ответ на этот вопрос о временной сложности алгоритма?

Question

Вопрос такой:

Я сказал, что это утверждение неверно, поскольку не существует констант k1 и k2 такой, что k1 * n <2 ^ log (n) + n ^ 3/2/30 ^ 30 + log (n) ^ 10 <k2 * n при <em>n становится достаточно большим.

У меня все еще есть проблемы с пониманием обозначения Big O, поэтому я не уверен, является ли это правильным обоснованием.

Answer 1

Предположим, что log означает log_10, логарифм в базе 10.И скажем lg обозначает логарифм в базе 2.Тогда

log n = (lg n)(log 2),

, что можно проверить, взяв log с обеих сторон n = 2^(lg n).

. Из первого уравнения мы выводим, что

2^(log n) = n^(log 2)

таким образомпервый член - θ(n^(log 2)), где log 2 ≈ 0.301.Второй член θ(n^1.5).Следовательно, сумма первых двух слагаемых равна θ(n^1.5).И поскольку n^1.5 также доминирует над (log n)^10, мы получаем, что ответом является θ(n^1.5).