Why you can’t spell “bOgOsOrt” without some “big O’s”…

There is a legendary sorting algorithm called “bogosort”. It takes an array and randomly shuffles it. It then checks if the array is sorted. If not, then it repeats.

That’s it. Eventually, the array will be sorted.

Bogosorting is magical. There is always a possibility that on the first shuffle, you’ll get the sorted array! Imagine that — sorting an array of 1 billion items in one step. Every other sorting algorithm pales in comparison.

So what is the problem? Unfortunately, the above scenario is the best case scenario. For an array just of length 10, each shuffle has a one in 3,628,800 chance of sorting the array. Add just one more element to the array, and that chance drops to 1 in 39,916,800. If we consider the worst case scenario for bogosort, we are going to have to shuffle the array millions of times to sort even very small arrays. Even humans, slow and dumb as we are, could do better than that.

This practice of considering the worst case scenario when evaluating the efficiency of algorithms is integral in computer science. We don’t want to rely on the fact that our algorithm is going to have favorable starting conditions. Take sorting for example. We want an algorithm that is as quick as possible, REGARDLESS of the initial state of the array.

We capture this “worst case” efficiency using what is called “big O” notation. Big O notation represents the efficiency of an algorithm by capturing how fast the number of steps in the increases with the size of the input in the least favorable starting conditions. How long will it take to sort the most “unsorted” array?

To better illustrate this, consider the array: [1, 2, 3, 4, 5, 6, 7, 8]. We are trying to write an algorithm that indicates if a specified element is in the array or not. If our specified element is 1, then the algorithm will take a single step. It will look at the first element, see that it is 1, and return true. No matter how many elements I tack on to the end of the array, this process will always take one step because of favorable starting conditions. But what if I am looking for an element that doesn’t exist in the array, like 0? The algorithm will have to look through the entire list of numbers before it can come to the conclusion that 0 is not in the array. If we add 8 more items to the list, this algorithm will take 8 more steps. Big O notation isn’t concerned with the first scenario, the best-case scenario. For this algorithm, the big O efficiency will reflect that in the worst case scenario, the number of steps that the algorithm takes will grow linearly with the number of items in the array.

Here are some common big O efficiencies for algorithms run on the array:

1. O(1), constant time: No matter how big the array is, the algorithm always takes the same amount of time. When the array length is tripled, the algorithm takes the same number of steps.
2. O(n), linear time: In the worst case scenario, the number of steps that the algorithm takes scales linearly with the length of the array. When the array length is tripled, the algorithm takes 3 times as many steps.
3. O(n²) quadratic time: In the worst case scenario, the number of steps that the algorithm takes scales quadratically with the length of the array. When the array length is tripled, the array takes 3² = 9 times as many steps.

The “time complexity” of our algorithm refers to what is inside the big O notation. When writing algorithms, we want to minimize time complexity, and use as few steps as possible to accomplish our goal.

This is why a strong knowledge of the different data structures in computer science is vital for writing algorithms. Consider a pair of examples:

1. Looking up a key in an object is O(1), while finding the location of a value in an array if O(n).
2. Consider being tasked to find all of the elements that are common to two arrays. If you compare the arrays to one another directly, this process will have O(n²) efficiency. But if you use an object intermediate, you can reduce the time complexity to O(n).

Here, we see that there is a serious advantage to using objects in algorithms. The above examples only consider objects and arrays, but there are many other data types which lends themselves to improving efficiency in different situations.

There is an old adage which advises us to “hope for the best, but expect the worst”. Certainly, if we were to separate these two clauses, you would be remiss to abide by the former rather than the latter when writing programs. If we rely on bogosort to sort our arrays, we are hoping for the best. Unfortunately, in computer science, it is much more important to expect the worst, and this is the utility of big O notation.