Analysis of Algorithms - Course Material
**Course Material: Analysis of Algorithms**
---
**Module 1: Introduction to Algorithm Analysis**
# **Learning Objectives**
- Understand the purpose of analyzing algorithms.
- Learn about time and space complexity.
- Explore real-world relevance through examples.
# **Theory**
When writing a program, we often think about whether it gives the correct result. But what
if you need to solve the same problem for millions of inputs? That’s where **algorithm
analysis** comes in. It helps us answer:
- How fast does it run?
- How much memory does it use?
- How does it behave for large input sizes?
We usually talk about:
- **Time complexity**: How the running time grows with input size `n`.
- **Space complexity**: How much additional memory is used.
We want to find the most efficient algorithm for a task!
---
**Module 2: Orders of Growth & Asymptotic Notation**
# **Learning Objectives**
- Use asymptotic notations to describe algorithm performance.
- Recognize common growth rates.
# **Theory**
Asymptotic notations describe the growth of time complexity as the input size `n`
approaches infinity.
## **1. Big-O Notation (O)**
Describes the **upper bound**. Worst-case.
> Example: `O(n^2)` means time grows proportional to the square of the input.
## **2. Big-Omega (Ω)**
Describes the **lower bound**. Best-case.
## **3. Theta (Θ)**
Describes the **tight bound** — both upper and lower.
## **4. Little-o and Little-ω**
Describes **strict** bounds.
# **Common Growth Rates (with Examples)**
| Name | Notation | Example Algorithm |
|--------------|-----------|-----------------------------|
| Constant | O(1) | Accessing an array element |
| Logarithmic | O(log n) | Binary Search |
| Linear | O(n) | Linear Search |
| Quadratic | O(n^2) | Bubble Sort |
| Cubic | O(n^3) | Matrix Multiplication |
| Exponential | O(2^n) | Recursive Fibonacci |
---
**Module 3: Worst, Best, and Average Case Analysis**
# **Learning Objectives**
- Understand different scenarios of algorithm performance.
# **Theory**
- **Best Case**: Minimum operations (e.g., Binary Search finds element in first try).
- **Worst Case**: Maximum operations.
- **Average Case**: Expected performance over all possible inputs.
## **Example: Linear Search**
int linearSearch(int a[], int n, int key) {
for (int i = 0; i < n; i++) {
if (a[i] == key) return i;
}
return -1;
}
**Module 4: Analyzing Control Structures**
# **Learning Objectives**
# **Theory & Examples**
if (n > 0)
x++;
else
x--;
for (int i = 0; i < n; i++)
sum += a[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
x++;
**Module 5: Recurrence Relations**
# **Learning Objectives**
# **Theory**
## **Substitution Method**
## **Change of Variable**
## **Master’s Theorem**
**Module 6: Analysis of Sorting & Searching Algorithms**
# **Learning Objectives**
# **1. Bubble Sort**
void bubbleSort(int a[], int n) {
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (a[j] > a[j+1])
swap(&a[j], &a[j+1]);
}
# **2. Insertion Sort**
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
a[j + 1] = a[j--];
a[j + 1] = key;
}
}
# **3. Linear Search**
# **4. Binary Search**
int binarySearch(int a[], int l, int r, int key) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == key) return mid;
if (a[mid] < key) l = mid + 1;
else r = mid - 1;
}
return -1;
}
**Module 7: Practice Questions**
# **Theory-Based**
# **Code-Based**
for (i = 1; i < n; i *= 2)
for (j = 0; j < n; j++)
x++;