Как рассчитать сумму лог-терминов с разной базой?

Question

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

(журнал ₂ n + 1) + (журнал ₃ n +2) + (log ₄ n + 3) + ..... + (log _n n + (n - 1))

Как можно изобразитьвремя сложность этого алгоритма с точки зрения обозначения «большой О»?

Answer 1

Рассмотрим сумму лог-терминов и не логарифмических терминов отдельно.

Среди лог-терминов log ₂ n является наибольшим и существует n-1 терминов.Следовательно, сумма меньше (n-1) log ₂ n, это в O (n log n).

Сумма не логарифмических терминов равна (n-1)) n / 2, это в O (n²).

Мы видим, что сумма не логарифмических членов доминирует над суммой логарифмических терминов.Следовательно, результат O (n²).