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

Question

It was interesting to me. What is the complexity of the algorithm that starts with n elements (which I execute anyway). I take off one element, I do it again. I take off another element and do it again until I have only one element left. is it O (n log n)? I can not visualize it ...

Answer 1

The renowned mathematician Gauss is said to have found a formula for this exact problem when he was in elementary school. And, as @Henry mentioned in the comments, this is:

Source: Wikipedia

Since the work is done for each record, i.e. O (1) is required for each "item". Therefore, the problem is O (n ^ 2).

Visualization (also Wikipedia ) can be seen as a semi-filled square:

Answer 2

To solve the complexity for O (n + n-1 + n-2 .... n times), we need to use the sum for the math formula, see this link

=> n+n+n...n times - (1+2+3...n times) => n^2- (n^2+n)/2 

Difficulty will be

 (n^2-n)/2