
Classify Algorithms based on growth rate (ignore the coefficients)
Consider the highest-order term when working with large input sizes.
Given a piece of code, we count the number of operations it performs. This allows us to compare the efficiency of different algorithms using the big-O notation and focusing on the best and worst cases.
for(int i=0; i<10; i++) => O(1)
Op();
for(int i=0; i<n; i++) => O(n)
Op();
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) => O(n^2)
Op();
for(int i=1; i<=n; i*=2) => O(logn) //changing 2 changes the base of the log
Op();
//If the inner loop depends on the outer loop => Trace and then find the sum
$$ \text{constant }<\text{ logarithmic }<\text{polynomial} < \text{exponential} < \text{factorial} < n^n $$
int search(int a[], int k, int n)
{
for (int i = 0; i < n; i++)
if (a[i] == k)
return i;
return -1;
}
If the array is sorted, we could put another condition to return -1 if the key is less than the current element but the worst case becomes $2n$

| Best Case | $1$ key comparison | k is the first element |
|---|---|---|
| Worst Case | $n$ comparisons | k is not in the array |

| Best Case | $2$ comparisons | k is at the mid |
|---|---|---|
| Worst Case | $2(\lfloor\log_{2}n \rfloor +1)$ | k is less than the first element |
int search(int a[], int k, int n) {
int lo = 0, hi = n-1;
while (lo <= hi) {
int mid = lo + (hi-lo) / 2;
if (k > a[mid]) lo = mid+1;
else if (k < a[mid]) hi = mid-1;
else if (k == a[mid]) return mid;
}
return -1;
}
To find the minimum and place it in its correct position (invariant). The flag helps in data moves if min is at index i.
void selection(int a[], int n) {
for (int i = 0; i < n-1; i++) {
int min_index = i; //traverse the array; i at current
for (int j = i+1; j < n; j++) //look for the minimum
if (a[j] < a[min_index])
min_index = j;
if (i != min_index) //swap current with minimum
swap(a[i], a[min_index]);
}}

| Total = $O(n^2)$ | Data Compares | Data Moves |
|---|---|---|
| Best Case | $\frac{1}{2}n(n-1)$ | $0$ |
| Worst Case | $\frac{1}{2}n(n-1)$ | $3(n-1)$ |
To insert the temporary value in an appropriate position to the portion left of that temporary value. Good with partially sorted arrays and random values.
void insertion(int a[], int n) {
for (int i = 1; i < n; i++) {
int temp = a[i];
int j = i-1;
while (j >= 0 && temp < a[j]) {
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}}

If every element is either in its correct position or only a few steps away from it, we need a few data comparisons and moves for every element.
| Data Compares | Data Moves | Total | |
|---|---|---|---|
| Best Case | $(n-1)$ | $2(n-1)$ | $O(n)$ |
| Worst Case | $\frac{1}{2}n(n-1)$ | $\frac{1}{2}n(n-1)+2(n-1)$ | $O(n^2)$ |
To compare the current element with the one after it (adjacent values) and swap the values to sort it properly
void bubble(int a[], int n) {
for (int i = 0; i < n-1; i++) {
bool swapped = false;
for (int j = n-1; j > i; j--) {
if (a[j] < a[j-1]) {
swap(a[j], a[j-1]);
swapped = true;
}}
if (!swapped)
break;
}}

The flag reduces the number of iterations to only $1$ in the best case.
| Data Compares | Data Moves | Total | |
|---|---|---|---|
| Best Case | $(n-1)$ | $0$ | $O(n)$ |
| Worst Case | $\frac{1}{2}n(n-1)$ | $3 \times\frac{1}{2}n(n-1)$ | $O(n^2)$ |
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. It consists of nodes such that each node contains a data field and a reference/pointer to the node next to it in the list. (It is preferred over array list with frequent insertion and deletion of elements)
Add_to_Head() |
Add_to_Tail() |
Remove_Head() |
Remove_Tail() |
Contains() |
|---|---|---|---|---|
| $O(1)$ | $O(1)$ | $O(1)$ | $O(n)$ | $O(n)$ |

Add_to_Head() |
Add_to_Tail() |
Remove_Head() |
Remove_Tail() |
Contains() |
|---|---|---|---|---|
| $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ | $O(n)$ |

A new concept was introduced in doubly linked lists implementation which is templated functions (generic programming) This allows us to create a function template whose functionality can be adapted to more than one type or class without repeating the entire code for each type.