Как они нашли нижнюю границу следующего кода?

Question

procedure stars(n)
     for i = 1, . . . , n do
     print “∗” i many times

Вопрос - Используя Ω-нотацию, опустите нижнюю границу времени пробега звезд, чтобы показать, что ваша верхняя граница на самом деле асимптотически тесна.

Решение - Для простоты предположим, что n четно.Мы опускаем количество звездочек, напечатанных во время итераций от n / 2 до n:

Я не понял, почему они идут от n/ 2 к п.Как мне сделать этот вопрос?

Answer 1

Для Omega не имеет значения, с чего вы начали!Единственное, что касается нижней границы, это то, что она должна быть меньше указанной суммы.Решение просто хочет найти жесткую нижнюю границу для суммы, так как сумма находится в Theta(n^2) (сумма равна n(n+1)/2).

Answer 2

Обратите внимание, что сумма составляет не сверх j / 2 , но более n / 2 .Для каждого n / 2 ≤ j ≤ n , n / 2 ≤ j , поэтому выполняется неравенство с возможным исключением n = 2 : полная сумматри, вторая сумма равна 2 ( не 2² / 4 = 1: ошибка в том, что начинается с n / 2 вместо n / 2 + 1 .)
Выбор n / 2 ( + 1 ) в качестве нижней границы для суммирования просто делает сумму удобно тривиальной в сочетании с тем, чтобы каждое слагаемое было равно n / 2..

Answer 3

Обратите внимание, что при суммировании от n/2 до n вы суммируете меньше элементов, поэтому это уравнение является правильным.

Это сделано для того, чтобы упростить выражение в конце и найтив частности ниже связаны.