Analysis of Algorithms

1_kO69dq_xml2q3o2NH9OZ3g.png

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 $$


Searching and Sorting

Linear vs. Binary Search:

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;
}

Selection Sort :

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)$

Insertion Sort:

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)$

Bubble Sort:

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)$

Lists

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)

Singly-Linked lists

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

Doubly-Linked lists

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.

Ordered Lists