Big O Notation — Direct Way
Big O notation is a mathematical notation used in computer science to describe the upper bound or worst-case scenario of an algorithm's time or space complexity.
Knowing Big O notation is crucial during coding interviews and also for delivering better solutions.
Have you ever used a slow application? It's annoying, right? This may be due to time and space complexity issues, let’s get deep into that and learn how to avoid it.
Types Of Growth Rate
In Big O notation, the letter "O" stands for "order of," and it is followed by a function that represents the upper bound of the algorithm's growth rate. For example:
O(1) represents constant time complexity, meaning that the algorithm's runtime or space requirements do not change with the input data size.
O(log n) represents logarithmic time complexity, where the algorithm's runtime or space requirements grow logarithmically as the size of the input data increases.
O(n) represents linear time complexity, where the algorithm's runtime or space requirements grow linearly with the size of the input data.
O(n^2) represents quadratic time complexity, where the algorithm's runtime or space requirements grow quadratically with the size of the input data.
O(1) - Constant Time Complexity
int[] array = {1, 2, 3, 4, 5};
int element = array[0]; // Accessing the first element of the array
Accessing an element in an array by index takes constant time, regardless of the size of the array.
O(log n) - Logarithmic Time Complexity
public static int binarySearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Element not found
}
Binary search in a sorted array reduces the search space by half with each comparison, resulting in a time complexity that grows logarithmically with the size of the array.
O(n) - Linear Time Complexity
public static int findMax(int[] array) {
int max = Integer.MIN_VALUE;
for (int num : array) {
if (num > max) {
max = num;
}
}
return max;
}
Finding the maximum element in an array requires iterating through each element once, resulting in a time complexity that grows linearly with the size of the array.
O(n^2) - Quadratic Time Complexity
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
The bubble sort algorithm compares and swaps elements multiple times, resulting in a time complexity that grows quadratically with the size of the array, making it less efficient for large datasets.
Time Complexity vs Space Complexity
In all the examples shown previously, we are talking about Time complexity, this means that the algorithms that have BigO(1) are much faster than BigO(n)².
Note that N makes a big difference, if there is only one element, the result will not be noticed, however, if you have thousands of elements, it can have a significant impact.
For space, complexity is very similar, the difference is that with space complexity we look for the amount of memory instead of the amount of time.
Time complexity: measures the amount of time an algorithm takes to run as a function of the size of its input.
Space complexity: measures the amount of memory (space) an algorithm requires to run as a function of the size of its input.
Reducing the complexity
I hope you understand that having high complexity can be a big problem and that you have understood the difference between space and time complexity.
To reduce complexity, the best way is to master data structure. I would rather not make this article so long, so I will share more about data structure in the next posts.
A great method to reduce complexity is to become familiar with it. It can be achieved by practicing coding challenges to improve your understanding of different solution types, enhance your coding interview skills, and become familiar with Big O notation.
Conclusion
Understanding space and time complexity is essential for developing scalable applications.
Production and test environments usually have a big difference in the number of data, and knowing Big O notation can save you from production bugs and slow applications.
I hope this article has helped you in some way, and if you want to keep updated with things that can help you deliver better solutions, please subscribe.