You don’t need to be a math whiz to be a good programmer, but there are a handful of tricks you will want to add to your problem solving bag to imp...
For further actions, you may consider blocking this person and/or reporting abuse
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) / 2This 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.
Sure, go ahead!
There is no excuse to forget the formula now!
I mean, you don't even need to list cases.
I suggest reading a good book about Discrete Mathematics. Currently I'm reading this one which is very helpful.
Revisiting those topics help you understand how useful they are in computers and computations.
But calculating the array length has a cost of O(N). At the end there is no improvement un complexity
Depends on the language...
Array length isn't "calculated" it's a property of the Array, so to get the Array.length it is just O(1).
This is really interesting. However the only thing I find IS that it depends on the implementation.
Could you please send a source? I'm really interested on how this property gets calculated
maybe joel is talking about javascript. Hes right its a property of an array. Thats how V8 implements it (sorry I cant find the link but Its in v8.dev). In other programming languages its still O(1) or constant time because it will do an arithmetic operation, example before c++14 (not sure) we do it in class was like
totalNumberOfbytesInArray / numberOfBytesInInt. or maybe im wrong because it was 2008. loolsWhen an item is added to or removed from the array, the length property is updated. You can check this by running this code:
lengthNEEDS to be a property, otherwise code like this would become exponential:I think this Tweet is relevant to the discussion:
I prefer the simpler proof:
S = 1 + 2 + 3 + . ... + n
S = n + (n-1) + (n-2) + ... + 1
2S = (n+1) + (n+1) + (n+1) + ... + (n+1) = n (n+1)
=> S = n (n+1)/2
Interestingly the formula is O(1) if you consider the addition/multiplication/division to be ATOMIC. But in reality such operations take O(N) time with regard to the LENGTH OF THE INPUT |N| which in this case is Log N.
So the algorithm really takes O(N) time with respect to INPUT SIZE rather than O(1) (but O(logN) time with respect to N's value if you consider the realities of the bitwise math operations). This becomes evident if you start using 1000 bit numbers for example.
This common confusion may lead people to believe that there's a polynomial time solution to the "efficient" fibonacci number:
(source: stackoverflow.com/questions/181722...)
But actually since the INPUT SIZE here is Log N, the algorithm is said to be "pseudo-polynomial" because its polynomial (O(N)) with regard to the value of N, but its actually EXPONENTIAL with regard to the input size Log N.
Again this becomes evident when you realize just how many bits you're going to need to represent that result.
Note: this probably has no bearing on your real world algorithm as long as you live within the confines of 32 bit of 64 bit numbers. :)
More on this confusing topic here: cs.stackexchange.com/questions/164...
npm i sum-numbers-in-array
Couldn't find that one, but this is close npmjs.com/package/array-sum
yeahh it was a joke hehe, thanks for the article btw. I liked it!
Anecdotally, this algorithm is said to be applied (and possibly developed) by young Gauss at his age of 10. :-)
Little Carl 🧒
Thanks for sharing this. I have been looking to improve my knowledge of algorithms.
Just subscribed to your newsletter.
Thanks and thanks!
cool!
Nice post, Jared.
Too complicated for me. 🤯
Hey dude, great article!
I'm just missing one thing
do i have to assume this list is always sorted?
This is just a formula for adding up the numbers 1 to n (the order you add numbers doesn't matter).
If you have a collection of numbers that you don't know the structure to (ie, it's not something as simple as an arithmetic sequence), there's no trick to adding them up faster that's faster than doing it one by one.
How about sum of any arithmetic series ?
varsitytutors.com/hotmath/hotmath_...
To find the sum of the first n terms of an arithmetic sequence use the formula,
Sn=n(a1+a2)/2 ,where n is the number of terms, a1 is the first term and an is the last term.
Find the sum of the first 40 terms of the arithmetic sequence : 2,5,8,11,14,⋯
First find the 40 th term: a40=a1+(n−1)d =2+39(3)=119
Then find the sum . 40(2+119) / 2 = 2420
Absolutely wonderful article for non maths major.