📌 Fibonacci Numbers & Tower of Hanoi
1️⃣ Fibonacci Numbers
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones:
🔹 Formula:
🔹 Base Cases:
🔹 Example Sequence:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
(a) Recursive Fibonacci (Simple but Inefficient)
🔹 Time Complexity: O(2^n)
(Exponential, slow)
🔹 Space Complexity: O(n)
(Recursive stack)
(b) Optimized Fibonacci (Using Iteration)
🔹 Time Complexity: O(n)
(Linear)
🔹 Space Complexity: O(1)
(Constant, no extra memory used)
(c) Fibonacci Using Dynamic Programming (Memoization)
🔹 Time Complexity: O(n)
(Faster than recursion)
🔹 Space Complexity: O(n)
(For memoization table)
2️⃣ Tower of Hanoi
The Tower of Hanoi is a mathematical puzzle where three pegs (A, B, C) and n disks must be moved while following these rules:
🔹 Rules:
1️⃣ Only one disk can be moved at a time.
2️⃣ A larger disk cannot be placed on a smaller disk.
3️⃣ The goal is to move all disks from peg A to peg C using peg B as an auxiliary.
🔹 Steps for n
Disks:
- Move
n-1
disks from A → B (using C). - Move the largest disk from A → C.
- Move
n-1
disks from B → C (using A).
🔹 Minimum Moves Required:
🔹 Example for n = 3
(Moves = 7
):
Recursive Solution for Tower of Hanoi
🔹 Time Complexity: O(2^n)
(Exponential)
🔹 Space Complexity: O(n)
(Recursive calls)
🚀 Summary Table: Fibonacci vs Tower of Hanoi
Problem | Approach | Time Complexity | Best Optimization |
---|---|---|---|
Fibonacci | Recursion | O(2^n) (Exponential) | Memoization (O(n) ) |
Fibonacci | Iteration | O(n) | Best for large n |
Tower of Hanoi | Recursion | O(2^n) | No major optimizations |
Tower of Hanoi | Iteration | Difficult to implement | Mostly solved using recursion |
No comments:
Post a Comment