Foundations
Mathematical Sequences
Difficulty: Beginner
Why is a triangular nested loop that does 1 + 2 + 3 + ... + n units of work classified as O(n^2) rather than O(n)? Because the closed form of that sum is n(n+1)/2, which grows quadratically. The same kind of summation argument explains...
Mathematical Sequences
Why is a triangular nested loop that does 1 + 2 + 3 + ... + n units of work classified as O(n^2) rather than O(n)? Because the closed form of that sum is n(n+1)/2, which grows quadratically. The same kind of summation argument explains why merge sort is O(n log n), why a doubling array gives amortized O(1) insertions, and why naive recursive Fibonacci is exponentially slow.
Mathematical Sequences equips you with the essential sequences and summation formulas behind algorithm analysis. You will work with arithmetic sequences (where each term adds a constant) and the formula 1 + 2 + ... + n = n(n+1)/2, geometric sequences (where each term multiplies by a constant ratio) and their geometric-series sum, and the Fibonacci sequence defined by F(n) = F(n-1) + F(n-2). You will then connect these formulas back to code: triangular nested loops, halving-and-doubling patterns, and the canonical recursive Fibonacci that motivates dynamic programming.
In Big-O Notation (Upper Bound), you learned to spot dominant terms and to drop constants and lower-order terms. This lesson supplies the closed-form summations that turn a step count like 1 + 2 + ... + n into a precise polynomial you can simplify with confidence.
With these summation tools in hand, you will be ready for Debugging by Tracing, where you will sharpen the step-by-step execution skills you need to verify that the algorithms you analyze actually behave the way your formulas predict.
Prerequisites:
Big-O Notation (Upper Bound)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Identify and generate arithmetic sequences given a first term and common difference.
Identify and generate geometric sequences given a first term and common ratio.
Apply the sum formula n(n+1)/2 and explain its connection to nested loop analysis.
State the closed-form sum of a geometric series and recognize when it applies.
Describe the Fibonacci sequence and its connection to recursion.
Why This Matters
01
The sum 1 + 2 + 3 + ... + n = n(n+1)/2 explains why nested loops are O(n^2).
02
Geometric sequences explain why divide-and-conquer algorithms like merge sort do O(n) work per level.
03
The Fibonacci sequence is the classic example of recursion and dynamic programming.
Key Terms
6 terms you'll encounter in this lesson
Arithmetic sequence
A sequence where each term differs from the previous by a constant amount (the common difference). Example: 2, 5, 8, 11, ... (common difference = 3).
Geometric sequence
A sequence where each term is multiplied by a constant ratio. Example: 1, 2, 4, 8, 16, ... (common ratio = 2).
Summation (sigma notation)
The total obtained by adding up all terms in a sequence. Written as a sum from i=1 to n of f(i).
n(n+1)/2
The sum of the first n natural numbers: 1 + 2 + 3 + ... + n. This formula appears constantly in algorithm analysis.
Fibonacci sequence
A sequence where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Defined by F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).
Geometric series sum
For a geometric sequence with first term a and ratio r (r != 1): sum = a * (r^n - 1) / (r - 1). When r = 2, the sum is approximately 2 * a * 2^(n-1).
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"The sum 1+2+3+...+n is O(n) because we add n numbers"
The sum itself equals n(n+1)/2, which is O(n^2). The number of additions is n, but the value of the sum grows quadratically. When this sum represents total loop iterations, the algorithm is O(n^2).
"Geometric sequences and arithmetic sequences are the same thing"
In arithmetic sequences, you ADD a constant each step (2, 5, 8, 11...). In geometric sequences, you MULTIPLY by a constant each step (1, 2, 4, 8, 16...). They grow very differently -- linear vs exponential.
"The Fibonacci sequence is just 1, 1, 2, 3, 5, 8"
The modern convention starts with F(0) = 0: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The key property is F(n) = F(n-1) + F(n-2), which makes it the poster child for recursion and DP.