This week, we will be exploring a highly significant topic for anyone with an interest in computer science. It is a subject so essential that it enables us to assess the efficiency and quality of algorithms. We are going to be looking at Big O.
What is the Big O?
In mathematical terms, Big O is a notation used to characterize the behaviour of a function as its input approaches a specific value or infinity. In simpler terms, it provides insight into how a function behaves when its input values become large and tend towards infinity.
To provide a clearer illustration, let's consider a scenario where you need to transfer a file to a friend who resides on the opposite side of the country. Initially, for smaller files, you would likely opt for electronic transfer methods such as email or FTP, taking into account factors such as internet speed and reliability. In this case, the transfer time could vary significantly, ranging from as short as 10 minutes to as long as 5 hours.
However, let's now envision a different scenario where the file size is a massive 1 terabyte (TB). With such a substantial file, depending once again on your internet conditions, it could take more than a day to complete the transfer electronically. In such circumstances, it becomes apparent that traveling to meet your friend in person and physically handing over the file would be a far more efficient option. Of course, this consideration assumes other practical factors are taken into account, and flying solely for file transfer may not be a reasonable choice.
In situations where flying is not feasible or cost-effective, embarking on a road trip to personally deliver the file emerges as a highly practical and efficient alternative. Compared to the arduous process of downloading the colossal file from the internet, driving directly to your friend's location would prove to be a significantly faster and more reliable approach.
In the given examples, we can observe two distinct methods for file transfer, each with its runtime considerations.
Transferring over the internet (electronically): The runtime complexity can be represented as O(n), where 'n' denotes the size of the file. This implies that the time required to transfer the file increases linearly with its size. For instance, if it takes 2 seconds to send a 5 MB file, it would take approximately 4 seconds or more to send a 10 MB file.
Driving or flying to the person: The runtime complexity, in relation to the file size, can be expressed as O(1). Irrespective of the file's magnitude, the time taken remains constant. Therefore, if it takes 10 hours to deliver a 1TB file, it would also take 10 hours to deliver a 10TB file.
In our presented scenario, we mention several popular runtime complexities encountered when developing algorithms: O(log n), O(n log n), O(n^2), and O(2^n). These notations denote the potential runtimes of algorithms we often encounter during the coding process.
Best Case, Worst Case, Expected Case
These describe various runtimes for an algorithm. Let's look at it from the perspective of the quick sort algorithm. In quick sort, we randomly select a number in the array as the 'pivot' and then swap elements such that elements less than appear before elements greater than appear after the pivot. It then recursively does the whole process again on either side of the pivot until it is fully sorted.
Best Case: If all the elements in the array are equal then the quick sort would on average, traverse the whole array once, that is in O(n) time with n being the number of elements in the array
Worst Case: This can happen if our pivot is repeatedly the biggest element in the array, Since we don't have control over picking the pivot as a result of the randomness, this can happen if the pivot is the first element in a reverse sorted array. In this case, our array is not divided into two halves on recursion, it only shrinks by one element (the pivot). Then we'd have a runtime of O(n^2).
Expected Case: In typical coding scenarios, extreme cases such as the best or worst cases rarely occur repeatedly. Instead, we usually encounter a balanced distribution of pivots that facilitate proper sorting. In this expected case, the runtime complexity of Quick Sort is estimated to be O(n log n), which signifies a more efficient sorting process.
Space Complexity
Indeed, alongside time complexity, space complexity plays a vital role in determining the efficiency and optimization of algorithms. When assessing the space complexity, we consider the amount of memory or space required by an algorithm to store and manipulate data.
In terms of space complexity, it is often directly proportional to the size of the input. For instance, when creating an array of 'n' elements, it requires O(n) space in memory to accommodate these elements. The space required increases linearly with the size of the input.
Similarly, if we employ a two-dimensional array, such as a matrix or a grid, the space complexity becomes O(n^2), where 'n' represents the size of the two-dimensional array. Consequently, as the size of the 2D array grows, the space required in memory increases quadratically.
By considering space complexity in addition to time complexity, we gain a more comprehensive understanding of the resource utilization and efficiency of algorithms. This enables us to design algorithms that optimize both time and memory usage.
Examples of Runtimes and their use-cases
As I mentioned in the first section, there are a couple of popular runtimes that we would encounter while writing algorithms, I want to mention a few and write alongside their use cases.
O(1): A constant runtime refers to an operation that is performed only once, without iterating through an array or a collection of elements. Examples of such operations include basic arithmetic calculations like addition or subtraction, where the execution time remains constant regardless of the input size
O(n): Linear runtime complexity is commonly encountered in algorithms that involve iterating or processing each element in a collection or performing operations on a data structure that scales with the input sizeAn example is when we are traversing a linked list.
O(n^2): This is known as quadratic runtime, when the time it takes to run the algorithm increases as the square of the input size, This can happen when the algorithm has to perform nested loops, or when it has to compare each element in an input array to every other element. An example is the bubble sort algorithm or brute-force search algorithm.
O(log n): An algorithm has a logarithmic runtime when the time it takes to run the algorithm increases as the logarithm of the input size. This can happen when the algorithm has to divide the input into smaller and smaller subproblems, or when it has to use a divide-and-conquer approach. An example is in tree traversals and the binary search algorithm.
O(2^n): This is known as exponential runtime when the time it takes to run the algorithm increases as an exponential function of the input size. This can happen when the algorithm has to perform recursive calls, or when it has to try every possible combination of values. We can get this runtime in recursive calls or graph traversal algorithms.
Throughout this article, we have explored the concept of Big O notation, delving into its meaning and significance. We have examined various runtime scenarios, including the best case, worst case, and expected case, in the context of algorithm analysis. Moreover, we have provided examples of different runtime complexities that commonly arise when developing algorithms.
By understanding Big O notation and considering different runtime scenarios, we gain insights into the efficiency and performance characteristics of algorithms. This knowledge proves invaluable when analyzing and optimizing code, allowing us to make informed decisions about algorithm selection and implementation.
For further reading, you can consult any book on algorithms, but my favourite go-to would be Cracking the Coding Interview by Gayle McDowell. which was very helpful in writing this article