re: Improve Your Algorithms with this Simple Equation VIEW POST


I also like the more visual geometric proof of this formula. Say you want the sum of 1-4, you can make this shape:


The area of this triangle is then equivalent to our original problem, the sum of the first 4 natural numbers. But, it's hard to find the area of this "triangle", but easy if you make a rectangle (#s are a second, rotated copy of the triangle)


This is a 5x4 rectangle, so its area is 20. The rectangle is made of two of the triangles we want to know the area of, so the sum is 20/2 = 10.

If you generalize this to the first n natural numbers, you do indeed get the formula n (n + 1) / 2


There is no excuse to forget the formula now!
I mean, you don't even need to list cases.


This is great! I sketched something similar in this post on quadratic complexity jarednielsen.com/big-o-quadratic-t..., but I like yours better. Do you mind if I use it? With credit, of course.

code of conduct - report abuse