Почему не совпадает сложность алгоритма?
Тут указана не сложность, а асимптотика. Т.е. Сумма натуральных чисел при росте n растёт как n^2
https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1...
Так получилось, что программисты обычно сталкиваются с этими обозначениями только в контексте сложности алгоритмов, но вообще-то это обычная математическая нотация
Сложность показывает сколько элементарных операций нужно сделать, чтобы решить задачу.
Если использовать цикл, то сложность будет порядка n операций (по числу итераций цикла), а если взять формулу суммы n первых членов арифметической прогрессии, то сложность будет не O(n*n), а порядка O(1), потому что при любом n по указанной формуле можно вычислить сумму  условно за одно умножение.