Design and Analysis of Algorithms (DAA) - Detailed
Notes
1) Linear Search
Definition: Linear Search checks each element sequentially until the key is found or the array
ends.
Pseudocode:
LinearSearch(A, n, key)
for i = 0 to n-1
if A[i] == key
return i
return -1
Dry Run Example:
Array: [10, 20, 30, 40], key = 30
Step1: Compare 10 (not match)
Step2: Compare 20 (not match)
Step3: Compare 30 (match found at index 2)
Time Complexity:
Best Case: O(1) (element at first position)
Worst Case: O(n) (element at last or not found)
C++ Implementation:
int linearSearch(int arr[], int n, int key){
for(int i=0;i<n;i++){
if(arr[i]==key) return i;
}
return -1;
}
2) Binary Search
Definition: Binary Search works on sorted arrays and repeatedly divides the search space into
half.
Pseudocode:
BinarySearch(A, low, high, key)
while low <= high
mid = (low+high)/2
if A[mid] == key return mid
else if key < A[mid] high = mid-1
else low = mid+1
return -1
Dry Run Example:
Array: [10,20,30,40,50], key=40
low=0 high=4 mid=2 → 30
40 > 30 → search right
low=3 high=4 mid=3 → 40 found
Time Complexity:
Best Case: O(1)
Worst Case: O(log n)
C++ Implementation:
int binarySearch(int arr[], int n, int key){
int low=0, high=n-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]==key) return mid;
else if(key<arr[mid]) high=mid-1;
else low=mid+1;
}
return -1;
}
3) Bubble Sort
Definition: Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
Pseudocode:
for i=0 to n-1
for j=0 to n-i-2
if A[j] > A[j+1]
swap(A[j], A[j+1])
Dry Run Example:
Array: [5,3,2]
Pass1: [3,5,2] → [3,2,5]
Pass2: [2,3,5]
Sorted
Time Complexity:
Best Case: O(n) (optimized)
Worst Case: O(n^2)
C++ Implementation:
void bubbleSort(int arr[], int n){
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
4) Selection Sort
Definition: Selection Sort selects the minimum element and places it at the correct position.
Pseudocode:
for i=0 to n-1
min=i
for j=i+1 to n-1
if A[j] < A[min]
min=j
swap(A[i], A[min])
Dry Run Example:
Array: [4,2,5]
Pass1: min=2 → swap → [2,4,5]
Sorted
Time Complexity:
Best Case: O(n^2)
Worst Case: O(n^2)
C++ Implementation:
void selectionSort(int arr[], int n){
for(int i=0;i<n-1;i++){
int minIndex=i;
for(int j=i+1;j<n;j++){
if(arr[j]<arr[minIndex])
minIndex=j;
}
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}
5) Merge Sort
Definition: Merge Sort is a Divide and Conquer algorithm that divides the array, sorts both halves,
and merges them.
Pseudocode:
MergeSort(A,l,r)
if l<r
m=(l+r)/2
MergeSort(A,l,m)
MergeSort(A,m+1,r)
Merge(A,l,m,r)
Dry Run Example:
Array: [4,2,5,1]
Divide → [4,2] [5,1]
Divide → [4][2] [5][1]
Merge → [2,4] [1,5]
Final Merge → [1,2,4,5]
Time Complexity:
Best Case: O(n log n)
Worst Case: O(n log n)
Recurrence: T(n)=2T(n/2)+O(n)
C++ Implementation:
void merge(int arr[], int l, int m, int r){
int i=l,j=m+1,k=0;
int temp[r-l+1];
while(i<=m && j<=r){
if(arr[i]<arr[j]) temp[k++]=arr[i++];
else temp[k++]=arr[j++];
}
while(i<=m) temp[k++]=arr[i++];
while(j<=r) temp[k++]=arr[j++];
for(i=l,k=0;i<=r;i++,k++)
arr[i]=temp[k];
}
6) Quick Sort
Definition: Quick Sort selects a pivot element and partitions the array around the pivot.
Pseudocode:
QuickSort(A,low,high)
if low<high
pi=partition(A,low,high)
QuickSort(A,low,pi-1)
QuickSort(A,pi+1,high)
Dry Run Example:
Array: [4,2,5,1]
Pivot=1
Partition → [1,2,5,4]
Recursively sort right side → [1,2,4,5]
Time Complexity:
Best Case: O(n log n)
Worst Case: O(n^2)
Recurrence: T(n)=T(k)+T(n-k-1)+O(n)
C++ Implementation:
int partition(int arr[], int low, int high){
int pivot=arr[high];
int i=low-1;
for(int j=low;j<high;j++){
if(arr[j]<pivot){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int temp=arr[i+1];
arr[i+1]=arr[high];
arr[high]=temp;
return i+1;
}