Big O Notation
Sorts, Time/Space Complexity, and Big O Exploration
x = 5 + (15*20);
y = 15-2;
print x + y;
for x in range (0, n);
print x;
- 2nd statement is O(1)
- so block of code is N*O(1)
- in other words O(N)
y = 5+(15*20);
for x in range(0,n):
print x;
for x in range (0,n):
for y in range (0,n):
print x * y;
- print statement is N * N --> O(N^2)
//practice
x = 5 + (15*20); --> O(1)
for x in range(0,n): --> O(N)
print x; O(1)+O(N) --> O(N)
for x in range(0,n): --> O(N)
for y in range(0,n): --> O(N)
print x * y --> O(N^2)
- What is the biggest? O(N^2), so it dominates.
if x > O: --> O(1)
else if x < 0: --> O(logn)
else: --> O(N^2)
- choose the largest runtime; O(N^2), b/c we look at the worst case scenario
- merge sort is a stable, recursive sorting algorithm
- breaks problems into subproblems (divide/conquer)
- reduces itself, keeps relative order (stable)
- array is divided into sub lists, creating entirely new arrays
-
- extra space is proportional to size of the list
- space complexity: O(N)
-
- space consumption is proportional to # of elements in list
- time complexity: O(nlogn)
- Merge sort: a sorting algorithm in which an array is divided and each half of the array is sorted and later merged into one array
- Another type of sort used on the AP Exam
- More complex
- Uses recursion (the technique that uses a method to call itself, more on recursion in Chapter 12)
- It’s like a divide-and-conquer
public class MergeSort {
static int comparisons = 0;
static int swaps = 0;
public static void mergeSort(int[] x) {
int[] temp = new int[x.length];
mergeSortHelper(x, 0, x.length - 1, temp);
}
public static void mergeSortHelper(int[] x, int lowIndex, int highIndex, int[] temp) {
if (lowIndex < highIndex) {
int mid = (lowIndex + highIndex) / 2;
mergeSortHelper(x, lowIndex, mid, temp);
mergeSortHelper(x, mid + 1, highIndex, temp);
merge(x, lowIndex, mid, highIndex, temp);
}
}
public static void merge(int[] x, int lowIndex, int mid, int highIndex, int[] temp) {
int l = lowIndex;
int m = mid + 1;
int n = lowIndex;
while (l <= mid && m <= highIndex) {
comparisons++; //white loop that merges the subarrays, each comparison is incremented
if (x[l] < x[m]) {
temp[n] = x[l];
l++;
} else {
temp[n] = x[m];
m++;
swaps++; //incremented every time the algorithm swaps two
//elements in order to put them in the correct order
//during the merging of two sub-arrays
}
n++;
}
while (l <= mid) {
temp[n] = x[l];
l++;
n++;
}
while (m <= highIndex) {
temp[n] = x[m];
m++;
n++;
}
for (n = lowIndex; n <= highIndex; n++) {
x[n] = temp[n];
}
}
public static void main(String[] args) {
final int TIMES = 12;
final int SIZE = 5000;
double sum = 0;
double time = 0;
for (int i = 0; i < TIMES; i++) {
int[] data = new int[SIZE];
for (int j = 0; j < data.length; j++) {
data[j] = (int) (Math.random() * 100000);
}
double startTime = System.nanoTime();
mergeSort(data);
double endTime = System.nanoTime();
sum += getSum(data);
time += endTime - startTime;
}
System.out.println("Average: " + sum / (TIMES * SIZE));
System.out.println("Total Seconds: " + time / 1000000000.0);
System.out.println("Comparisons: " + comparisons);
System.out.println("Swaps: " + swaps);
}
public static double getSum(int[] data) {
double sum = 0;
for (int i = 0; i < data.length; i++) {
sum += data[i];
}
return sum;
}
}
MergeSort.main(null);
System.nanoTime() is typically used for measuring elapsed time with high precision, as it has a resolution of nanoseconds. It is useful for measuring the duration of short tasks or for measuring the performance of small code snippets, such as in the given code snippet where it is used to measure the execution time of the mergeSort method for an array of size 5000.
- worst-case time complexity of Insertion Sort is O(n^2)
- where n is the number of elements in the array
- the number of operations required to sort the array increases quadratically as the size of the array increases
Insertion sort: a sorting algorithm in which smaller elements are inserted before larger elements
- A little less intuitive
- Compares first two elements
- Depending on comparison, inserts the second value ‘in front’ of the first value into index 0, moving first value into index 1
- First two are sorted
- Third element is checked, inserting continues
- Note: just like in selection sort, an already-sorted element remains in its current position
public class InsertionSort {
static int comparisons = 0;
static int swaps = 0;
public static void insertionSort(int[] x) {
for (int i = 1; i < x.length; i++) {
int temp = x[i];
int j = i - 1;
comparisons++; //comparisons incremented through for loop
while (j >= 0 && x[j] > temp) {
x[j + 1] = x[j];
j--;
swaps++; //increments swaps through while loop
}
x[j + 1] = temp;
}
}
public static void main(String[] args) {
final int TIMES = 12;
final int SIZE = 5000;
double sum = 0; //double b/c int might be too short
double time = 0;
for (int i = 0; i < TIMES; i++) {
int[] data = new int[SIZE];
for (int j = 0; j < data.length; j++) {
data[j] = (int) (Math.random() * SIZE);
}
double startTime = System.nanoTime();
insertionSort(data);
double endTime = System.nanoTime();
sum += calculateSum(data);
time += endTime - startTime;
}
System.out.println("Average: " + sum / (TIMES * SIZE));
System.out.println("Total Seconds: " + time / 1000000000.0);
System.out.println("Comparisons: " + comparisons);
System.out.println("Swaps: " + swaps);
}
private static double calculateSum(int[] data) {
double sum = 0;
for (int j = 0; j < data.length; j++) {
sum += data[j];
}
return sum;
}
}
InsertionSort.main(null);
- time complexity of Selection Sort is O(n^2)
- where n is the number of elements in the array
- number of operations required to sort the array increases quadratically as the size of the array increases
Selection sort: a search-and-swap algorithm
- The sort first traverses the array for the lowest value
- Once the sort finds this value, it swaps its position in the array with the data at index 0
- Now the first element is sorted
- The process then repeats for index 1: the rest of the array is searched for the lowest value, then swapped with the data at index 1
- Note: if lowest value is already in position, it stays there
public class SelectionSort{
static int comparisons = 0;
static int swaps = 0;
// Keep track of the number of comparisons and swaps made during sorting
// Sort an array of integers in ascending order using Selection Sort algorithm
public static void selectionSort(int[] numbers) {
// Loop through the array
for(int i = 0; i < numbers.length - 1; i++) {
// Set the current position to i
int position = i;
// Loop through the rest of the array and find the minimum element
for(int k = i + 1; k < numbers.length; k++) {
// Increment comparison counter
comparisons++;
// If the current element is smaller than the minimum element found so far, update the position
if (numbers[k] < numbers [position]) {
position = k;
}
}
// Swap the minimum element with the current element
swaps++;
int temp = numbers[i];
numbers[i] = numbers[position];
numbers[position] = temp;
}
}
public static void main(String[] args) {
final int TIMES = 12;
final int SIZE = 5000;
double sum = 0; //double b/c int might be too short
double time = 0;
for (int i = 0; i < TIMES; i++) {
int[] data = new int[SIZE];
for (int j = 0; j < data.length; j++) {
data[j] = (int) (Math.random() * SIZE);
}
double startTime = System.nanoTime();
selectionSort(data);
double endTime = System.nanoTime();
sum += calculateSum(data);
time += endTime - startTime;
}
System.out.println("Average random: " + sum / (TIMES * SIZE));
System.out.println("Total Seconds: " + time / 1000000000.0);
System.out.println("Comparisons: " + comparisons);
System.out.println("Swaps: " + swaps);
}
private static double calculateSum(int[] data) {
double sum = 0;
for (int j = 0; j < data.length; j++) {
sum += data[j];
}
return sum;
}
}
SelectionSort.main(null);
import java.util.Arrays;
public class bubbleSort {
static int comparisons = 0;
static int swaps = 0;
// Function to analyze Bubble Sort algorithm
public static void analyzeBubbleSort(int[] arr) {
final int TIMES = 12;
final int SIZE = 5000;
double sum = 0;
double time = 0;
for (int i = 0; i < TIMES; i++) {
int[] data = new int[SIZE];
for (int j = 0; j < data.length; j++) {
data[j] = (int) (Math.random() * SIZE);
}
double startTime = System.nanoTime();
bubbleSort(data);
double endTime = System.nanoTime();
sum += calculateSum(data);
time += endTime - startTime;
}
System.out.println("Average random: " + sum / (TIMES * SIZE));
System.out.println("Total Seconds: " + time / 1e9);
System.out.println("Comparisons: " + comparisons);
System.out.println("Swaps: " + swaps);
}
// Bubble Sort algorithm
public static void bubbleSort(int[] arr) {
boolean swapped;
for (int i = 0; i < arr.length - 1; i++) {
swapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
comparisons++; //increments comparisons through for loop
if (arr[j] > arr[j + 1]) {
swaps++; //increments swaps post-comparisons
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
private static double calculateSum(int[] data) {
double sum = 0;
for (int j = 0; j < data.length; j++) {
sum += data[j];
}
return sum;
}
public static void main(String[] args) {
int[] arr = new int[]{5, 2, 8, 1, 3};
analyzeBubbleSort(arr);
}
}
BubbleSortAnalysis.main(null);
| Sort | # Of Swaps | # Of Comparisons | Time (in seconds) | Numbers Average |
|---|---|---|---|---|
| Merge | 325104 | 662893 | 0.0107264 | 49878.481316666664 |
| Bubble | 299313505 | 599684745 | 0.4052764 | 2498.667033333333 |
| Insertion | 74848858 | 59988 | 0.0753918 | 2490.5959333333335 |
| Selection | 59988 | 149970000 | 0.2009398 | 2498.2385 |
Based on the data provided in the table, it appears that Merge sort is the fastest sorting algorithm with the lowest execution time of 0.0107264 seconds, while Bubble sort is the slowest with an execution time of 0.4052764 seconds.
Although Bubble sort and Selection sort have fewer comparisons than Merge sort, the number of swaps they perform is much higher, which leads to a significant increase in execution time. On the other hand, Merge sort uses a divide-and-conquer approach that reduces the number of swaps and comparisons required to sort the data.
Insertion sort, although it has a relatively low number of swaps and comparisons, its average execution time is still higher than Merge sort due to its sequential nature.
Therefore, it can be concluded that Merge sort is the most efficient sorting algorithm for sorting large datasets with a random distribution, followed by Insertion sort, Selection sort, and Bubble sort in decreasing order of efficiency.