Вопросы о расчете сложности времени

Question

Я пытался решить этот вопрос, и я знаю, что ответ должен быть O (n ^ 2) и омега (n ^ 2).Но решение для части b немного сбивает с толку.Я не знаю, почему нам нужно выбрать n / 2 для расчета омега.Может ли кто-нибудь любезно сказать мне причину?

Answer 1

n / 2 - это среднее значение i.

Это потому, что я переходит от 1 к n:

Суммируем все значения i, которые вы получаете n * (n + 1)/ 2, разделите это на n, чтобы получить среднее значение i (потому что вы используете в общей сложности раз), и вы получите n / 2 + 1/2 ~ = n / 2.