---

📘 Greedy Approach

(Basic Algorithm Design Technique)

1️⃣ Introduction

The Greedy approach is an algorithm design technique in which a solution is built step by step by making the locally optimal choice at each stage, with the hope that these local choices lead to a globally optimal solution.

A greedy algorithm never reconsiders its decisions once they are made.

---

2️⃣ Key Idea of Greedy Approach

At each step:

• Select the best available option
• Do not look ahead or backtrack
• Move towards the final solution

✔ Simple
✔ Fast
✖ Not always optimal for every problem

---

3️⃣ Characteristics of Greedy Algorithms

A problem must satisfy the following properties to be solved optimally using greedy approach:

🔹 1. Greedy Choice Property

A globally optimal solution can be obtained by making a locally optimal choice.

🔹 2. Optimal Substructure

An optimal solution contains optimal solutions to its sub-problems.

---

4️⃣ General Steps of Greedy Algorithm

1. Start with an empty solution
2. At each step, choose the best candidate
3. Add it to the solution
4. Repeat until solution is complete

---

5️⃣ Generic Greedy Algorithm (Pseudo-code)

Greedy(A):
   solution = empty
   while solution not complete:
       choose best candidate from A
       if candidate is feasible:
           add candidate to solution
   return solution

---

6️⃣ Examples of Greedy Algorithms

---

🔹 1. Activity Selection Problem

• Select maximum number of non-overlapping activities
• Choice: activity with earliest finishing time

Time Complexity: O(n log n)

---

🔹 2. Fractional Knapsack Problem

• Items can be divided
• Choice: highest value/weight ratio

Time Complexity: O(n log n)

---

🔹 3. Minimum Spanning Tree (MST)

(a) Kruskal’s Algorithm

• Select minimum weight edges
• Avoid cycles

Time Complexity: O(E log E)

(b) Prim’s Algorithm

• Expand tree from a vertex
• Choose minimum weight edge

Time Complexity: O(E log V)

---

🔹 4. Dijkstra’s Shortest Path Algorithm

• Finds shortest path from a source vertex
• Greedy choice: closest unvisited vertex

Time Complexity: O(V²) / O(E log V)

---

7️⃣ Advantages of Greedy Approach

✔ Easy to implement
✔ Efficient (low time complexity)
✔ Suitable for real-time systems
✔ Uses less memory

---

8️⃣ Disadvantages of Greedy Approach

✖ May not produce optimal solution
✖ Difficult to prove correctness
✖ Not applicable to all problems

📌 Example where greedy fails:

• 0/1 Knapsack Problem
• Coin Change problem (in some cases)

---

9️⃣ Greedy vs Dynamic Programming

Feature	Greedy	Dynamic Programming
Decision	Local	Global
Reconsideration	No	Yes
Optimality	Not always	Guaranteed
Complexity	Lower	Higher

---

🔟 Exam-Oriented Key Points

• Greedy makes local optimal choices
• Works only if problem satisfies greedy choice property
• Faster than DP
• Common in graph algorithms

---

🔚 Conclusion

The Greedy approach is a powerful and efficient algorithm design technique, but it must be applied carefully.

Greedy algorithms are fast and simple, but correctness depends on problem structure.

---