Может ли кто-нибудь проверить мои ответы на анализ Asymptoti c?

Question

Это для структуры данных и алгоритмов курса. Я уверен во всех из них, но часть d, и я не уверен, как приблизиться к e. Для части е я знаю, что это сумма ряда гармоник c, и наш профессор сказал нам, что он ограничен (ln (n) + 1 / n, ln (n) + 1), поскольку нет закрытой формы представление для суммы ряда гармоник c, но я все еще не уверен, как понять, у кого есть более высокая или более низкая скорость роста, чтобы определить, как их классифицировать. Если бы кто-то мог просмотреть мои ответы и помочь мне понять часть е, я был бы признателен за это. Спасибо.

Вопрос: https://imgur.com/a/mzi0LL9 Мои ответы: https://imgur.com/a/yxV6pim

Answer 1

Любая функция вида n^a a > 0"> будет доминировать в подобном ряду. Мы можем вычленить константу, чтобы увидеть, что немного проще, и такая серия общих гармоник c ограничена сверху логарифмом.

Итак, очевидно, мы можем игнорировать 200 в big-O. Вместо доказательства, так как кажется, что оно не требуется, вы можете подумать об интуиции, стоящей за ним. Суммирование при увеличении n будет продолжать добавлять все меньшие и меньшие члены, но будет продолжать расти до точки, где массивна, но 1 / n практически равна нулю.