📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 1 – INTRODUCTION & SORTING TECHNIQUES ) university of allahabad

cx 

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS

🔴 UNIT 1 – INTRODUCTION & SORTING TECHNIQUES

---

1️⃣ Introduction to Algorithms

✅ What is an Algorithm?

An algorithm is a finite set of well-defined steps used to solve a problem.

✅ Characteristics of Algorithm

✔ Input
✔ Output
✔ Finiteness
✔ Definiteness
✔ Effectiveness

---

2️⃣ Analysis of Algorithms

Algorithm analysis means measuring performance in terms of:

🔹 Time Complexity

Time taken by an algorithm to run.

🔹 Space Complexity

Memory used by the algorithm.

---

3️⃣ Growth of Functions

Used to compare algorithm efficiency.

Common Growth Rates:

Notation	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linear-log
O(n²)	Quadratic
O(2ⁿ)	Exponential

---

4️⃣ Asymptotic Notations

🔹 Big-O Notation – Worst Case

O(n)

🔹 Omega (Ω) – Best Case

Ω(n)

🔹 Theta (Θ) – Average Case

Θ(n)

---

5️⃣ Recurrence Relations

A recurrence relation defines a function in terms of itself.

Example:

T(n) = T(n/2) + n

Solution Methods:

✔ Substitution method
✔ Recursion tree
✔ Master theorem

---

6️⃣ Sorting Algorithms

---

🔹 1. Shell Sort

Idea:

Improvement over insertion sort by comparing distant elements.

Steps:

1. Choose gap

2. Compare elements

3. Reduce gap

4. Repeat

Time Complexity:

• Best: O(n log n)

• Worst: O(n²)

---

🔹 2. Quick Sort

Concept:

Divide and conquer algorithm.

Steps:

1. Choose pivot

2. Partition array

3. Recursively sort subarrays

Time Complexity:

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

---

🔹 3. Merge Sort

Concept:

Divide array → Sort → Merge

Steps:

1. Divide array into halves

2. Recursively sort

3. Merge sorted parts

Time Complexity:

O(n log n)

Advantage:

✔ Stable
✔ Predictable time

---

🔹 4. Heap Sort

Based on:

Binary Heap

Steps:

1. Build heap

2. Extract max/min

3. Reheapify

Time Complexity:

O(n log n)

---

🔹 5. Counting Sort (Linear Sorting)

Used when:

• Elements are in limited range

Time Complexity:

O(n + k)

---

7️⃣ Comparison of Sorting Algorithms

Algorithm	Best	Worst	Stable
Bubble	O(n)	O(n²)	Yes
Selection	O(n²)	O(n²)	No
Insertion	O(n)	O(n²)	Yes
Quick	O(n log n)	O(n²)	No
Merge	O(n log n)	O(n log n)	Yes
Heap	O(n log n)	O(n log n)	No

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 1)

✔ Define algorithm
✔ Explain asymptotic notations
✔ Explain quick sort with example
✔ Compare merge sort and quick sort
✔ Explain recurrence relation