Какая сложность алгоритма (относительно n)?

Question

[KuzmenkoArtem]

Все привет!
Кто знает как описать сложность этого алгоритма?

k = 0
for(i = n / 2; i < n; i++)
    for(j = 0; j < i; j++)
        k = k + n / 2

Буду благодарен за краткое объяснение, но можно и просто результат, если что потом разберусь, с решением будет проще
Заранее спасибо!

UPD: Нашел варианты ответов
0(n)
0(n/2)
O (n log(n))
O(n^2)

Comments

[atoro]

Я как человек недавно осиливший "Грокаем алгоритмы" в качестве первой в жизни книги на тему О-нотации, предположил бы 0(N*N), т.к. в обоих циклах идёт линейный (или последовательный?) перебор элементов, а тонкости вида n/2 в О-нотации вроде отбрасываются как малозначащие. Буду рад услышать в чём я не прав.

Answer 1

[Mercury13]

O(n²), разумеется.
Первый цикл выполняется O(n) раз, и второй O(n). Так что O(n²).
Если быть точнее, те итерации, которые выполнятся,— это трапеция на квадрате n×n, никакого тебе O(n), O(n log n) и подобного не будет.
Кстати, запись O(n/2) и O(n²/2) не имеет особого смысла — само определение символов Ландау говорит, что разница в константу не играет роли. По той же причине пишут O(n log n), не указывая, по какому основанию логарифм.

UPD2. Запись O(n²) означает: «не превышает cn² при стремлении n→∞». Так что всё, что O(n), одновременно и O(n²). И «никакого тебе O(n)» означает, что оценку n² мы улучшить не можем.

Answer 2

[Иван Клименко]

Конечно же O(n^2). Нотация O-большое съедает все константы.

Почему квадратичность? Потому что в каждом проходе внешнего цикла запускается проход внутреннего цикла, а количество итераций в каждом цикле зависит от n.