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

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² мы улучшить не можем.

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

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