Math for coding interviews/Summation - adding up a series
1+2+...+n = n(n+1)/2, Explained Simply
1 + 2 + 3 + ... + n always equals n×(n+1)/2. For n=10 that is 55. For n=100 that is 5,050. This is approximately n²/2 - which Big-O rounds to O(n²).
See it for yourself
Stack bars of height 1, 2, 3, 4... They form a triangle. A triangle is half a square (n×n), so the total is roughly n²/2.
Summation - adding up a series
1 + 2 + 3 + ... + n always equals n×(n+1)/2. For n=10 that is 55. For n=100 that is 5,050. This is approximately n²/2 - which Big-O rounds to O(n²).
Think of it this way: Stacking cannon balls in a triangle. The bottom row has n balls, the next has n-1, the next has n-2. Total balls = n(n+1)/2.
For algorithms: When an outer loop runs n times and an inner loop runs 1 time on the first pass, 2 on the second, 3 on the third... the total work is this triangle sum: O(n²).
Real-world analogy
Stacking cannon balls in a triangle. The bottom row has n balls, the next has n-1, the next has n-2. Total balls = n(n+1)/2.
Why it matters in interviews
When an outer loop runs n times and an inner loop runs 1 time on the first pass, 2 on the second, 3 on the third... the total work is this triangle sum: O(n²).