Это так называемая асимптотическая сложность — сложность при n→∞.
Что никто не упомянул — так называемые символы Ландау.
a(n) = o(b(n)), (читается «о малое», «меньшего порядка чем»), если lim{n→∞}a/b = 0
a(n) = O(b(n)), (читается «о большое», «не большего порядка чем»), если a/b ограничено сверху (для дискретного n этого хватит, для непрерывного надо добавить «для какого-то n>N»).
Два символа Дональда Кнута дополняют символы Ландау.
a(n) = Ω(b(n)), если b(n) = O(a(n)). «Не меньшего порядка чем»
a(n) = Θ(b(n)), если a(n) = O(b(n)) и b(n) = O(a(n)). «Такого же порядка».
Ну а дальше идут простые пределы.
• axn + bxn−1 + … = O(cxk + dxk−1 + …), если n ≤ k;
• те же два многочлена o(·), если n < k.
• те же два многочлена Θ(·), если n = k.
Константа не важна: во-первых, при n→∞ меньшая сложность рано или поздно перевесит меньшую константу. Во-вторых, особенности реализации того или иного алгоритма на том или ином компиляторе/железе (больше/меньше команд, лучше/хуже с кэшем) эту константу могут варьировать в широких пределах;
А значит, многочлен n(n−1)/2 = n²/2 − n/2 = Θ(n²).
Да, и ещё: вы спутали асимптотический порядок самогó многочлена и асимптотическую сложность его вычисления. Первое, как я уже сказал, n². Сложность вычисления в лоб — n+const = O(n). А «не в лоб» — «за константу» , O(1).
Средний
