Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Big-O complexity for n + n-1 + n-2 + n-3 + (...) + 1

Tags:

I was wondering.. what is the complexity of an algorithm that starts with n elements (which I run through doing whatever). I take one element off, I do it again.. I take off another element and do it again until I have just one element left. is it O(n log n)? I can't visualize it...

like image 812
Laura Martins Avatar asked May 30 '17 02:05

Laura Martins


1 Answers

The famous mathematician Gauss is said to have found a formula for that exact problem when he was in primary school. And as mentioned by @Henry in the comments it is: enter image description here

Source: Wikipedia (DE), Wikipedia (EN)

As work is done for every entry, i.e., O(1) is required for each "item". Hence, the problem is in O(n^2).

Visualisation (also Wikipedia) can be seen as a half filled square: enter image description here

like image 199
gue Avatar answered Oct 02 '22 17:10

gue