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

Question

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...

@Henry While I agree about the sum there are n terms here, thus it is O(n), not O(n^2). — Loren Pechtel, May 30 '17 at 03:57
@LorenPechtel no, "which I run through doing whatever" implies you do O(n) work for the first term alone. In total this gives then O(n^2). — Henry, May 30 '17 at 04:16
I read it as processing the term in some fashion, not as in processing something that number of times. — Loren Pechtel, May 30 '17 at 04:18
@LorenPechtel if you can process the n Elements in O(1), then you are of course right. But I don't think this is what's meant. Up to the OP to clarify. — Henry, May 30 '17 at 04:21
I'm voting to close this question as off-topic because it essentially comes down to the math question of what the result of the given sum is. — Bernhard Barker, May 30 '17 at 06:54
Possible duplicate of question https://stackoverflow.com/questions/9252891/big-o-what-is-the-complexity-of-summing-a-series-of-n-numbers — KRoy, Dec 17 '17 at 23:22

gue · Accepted Answer · 2021-06-06T07:58:32.260

42

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:

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:

edited Jun 06 '21 at 07:58

answered May 30 '17 at 07:08

gue

1,868
1
16
21

Great answer and visualisation link, really helped :) – Jordan Mackie Aug 05 '19 at 11:04
n squared is just the formula that gives you the final answer. How does that make it the time complexity of the algorithm. For example, if you multiply the input by 2 (aka scale it to twice its size), the end result is twice n squared. So as you grow the input, the end result scales by the factor you grow your input by. Isn't that linear ? – adityah Jul 23 '20 at 01:42
1

*Note, the above links are from de.wikipedia.org. In Chrome on PC you can click the translate button (to the right of Chrome's URL) to read the page in English.* Closest English Wikipedia entries I could find: https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF and https://en.wikipedia.org/wiki/Triangular_number – Gamepad.Coder May 23 '21 at 20:01
1

@Gamepad.Coder thx for that, I added your 2nd ref, as I also did not find a translated version of the German wiki-site. – gue Jun 06 '21 at 08:00
1

@adityah constants are not relevant for complexity evaluation, i.e., scaling by a constant factor can be ignored, https://en.wikipedia.org/wiki/Big_O_notation – gue Jun 06 '21 at 08:02

score 3 · Answer 2 · edited Oct 04 '19 at 13:37

3

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

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

Complexity will be

(n^2-n)/2

edited Oct 04 '19 at 13:37

EsmaeelE

2,331
6
22
31

answered Oct 04 '19 at 10:17

Deepak Gupta

31
1

1

Strictly speaking, shouldn’t you drop the constant and leave only the dominant term? Hence `(n^2-n)/2` would end up having a complexity of `n^2` or `O(n^2)`. In other words saying that the complexity will be `(n^2-n)/2` is incorrect. – 10110 Jan 07 '21 at 05:45

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

2 Answers2

Linked