WikiGalaxy
Big Omega and Big Theta Notation
Understanding Big Omega Notation (Ω):
Big Omega notation, denoted as Ω, provides a lower bound for the time complexity of an algorithm. It gives the best-case scenario performance, ensuring that the algorithm takes at least a certain amount of time to execute.
Example 1: Linear Search
In a linear search algorithm, the best case occurs when the target element is the first element of the list. This scenario gives us a time complexity of Ω(1).
int linearSearch(int[] arr, int x) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
Console Output:
Element found at index 0
Big Theta Notation (Θ)
Understanding Big Theta Notation (Θ):
Big Theta notation, represented as Θ, provides both an upper and lower bound on the time complexity of an algorithm. It indicates that the algorithm's runtime grows at the same rate for both the best and worst cases.
Example 2: Insertion Sort
The insertion sort algorithm has a time complexity of Θ(n²) in both the average and worst-case scenarios due to the nested loops involved in sorting.
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Console Output:
Sorted array: [1, 2, 3, 4, 5]
Complexity Analysis with Big Omega
Example 3: Binary Search
Binary search is a classic example where the best case is when the middle element is the target, resulting in a time complexity of Ω(1).
int binarySearch(int[] arr, int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
Console Output:
Element found at index 3
Complexity Analysis with Big Theta
Example 4: Merge Sort
Merge sort has a time complexity of Θ(n log n) for all cases due to its divide and conquer approach, ensuring consistent performance.
void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
Console Output:
Sorted array: [1, 2, 3, 4, 5]
Complexity Analysis with Big Omega and Theta
Example 5: Quick Sort
Quick sort is an interesting algorithm where the average and best-case time complexity is Θ(n log n), but the worst case can degrade to O(n²). However, with good pivot selection, it performs optimally most of the time.
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;
}
void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Console Output:
Sorted array: [1, 2, 3, 4, 5]
