Fibonacci Sequence

Easy

Fibonacci Sequence

DP basics: Efficiently compute by reusing previous values

📊 Complexity

Type	Value
Best	O(n)
Average	O(n)
Worst	O(n)
Space	O(n)

🏷️ Tags

DPMemoizationRecurrence

📖 Introduction

The Fibonacci sequence creates each number by adding the two preceding numbers. It is the most basic example of Dynamic Programming (DP), where you store and reuse previously calculated values.

1/18

📋Start!

Create a DP table of size 9 to calculate fib(8).

Basics

Fibonacci Sequence

Definition

The Fibonacci sequence creates each number by adding the two preceding numbers. It is the most basic example of Dynamic Programming (DP), where you store and reuse previously calculated values.

Key Characteristics

✓Recurrence: fib(n) = fib(n-1) + fib(n-2)
✓Base cases: fib(0) = 0, fib(1) = 1
✓Eliminate redundant calculations: Never compute the same value twice
✓Bottom-up approach: From smaller to larger problems

Time Complexity

Best

O(n)

Average

O(n)

Worst

O(n)

Space Complexity

O(n)

Fibonacci Sequence | AlgoNote