Fibonacci

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.

Naive recursive Fibonacci computes `fib(40)` in seconds, `fib(50)` in minutes, and gives up on `fib(60)`, all because it recomputes the same subproblems exponentially many times. Cache the result of each `fib(k)` the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming. **Dynamic Programming (Intro)** turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does `dp[i]` represent?"), write the transition ("how does `dp[i]` follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops `O(n)` to `O(1)`. In **Recursion Fundamentals**, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately. Next, **Bit Manipulation (Intro)** turns to a different toolkit, where bitwise operators give elegant `O(1)` solutions.