The Big O

In this very brief introduction to "Big O" notation, we hope to introduce you to the basic concepts that won't leave you "Crying" or even"Running Scared"

We're so used to computers nowadays doing things in the blink of an eye, that it's hard to think of them taking any time at all! But they do - and if it's a big and complicated calculation it can still take a noticeable time - even on your super-duper high power overclocked gaming rig or a Cray Supercomputer. The "Big O" notation ('O' comes from 'Order of magnitude if you're interested) is an attempt to express the complexity of solving something based on the input size.

Let's try an illustrate this with a literary example away from computers for a moment : the classic novel "A Christmas Carol" is only 28,000 words long. You can read it in an evening over a few bottles of your favourite ale. By contrast, "War and Peace" is 598,000 words long (although even that pales into insignificance compared to "Men of Goodwill" which is over 2 millions words long.)

Now - let's pose the question : what is the first word of Chapter One in each book? You will see that regardless of the length of the book (provided you have them to hand in your bookcase and don't have to download them first), you can answer that question in the same amount of time for each book. I can flip open "A Christmas Carol" and see the first word "Marley" just as quick as I can flip open "War and Peace" and read the first word "Well". Despite the fact that War and Peace is a much, much thicker book.

In big O notation, we say this problem has complexity O(1) - ie answering the question takes the same amount of time regardless of the size of the input.

Now let's move on to the next question. For each of these novels, tell me if the novel contains the word "complexity"?

In order to do that, we're going to have to sit there and read through the novels and have a look. We might hit it lucky! - "A Christmas Carol" might start with the sentence "Marley was dead to begin without complexity" in which case we're home and dry. Then again, it might not. (hint : it doesn't!) Big O notation is based on the *worst case scenario* ie that we're going to have to read through the entire book in each case. So you can see that because "War and Peace" is about 20 times as long as "A Christmas Carol" then theoretically it's going to take 20 times as long to answer that question. A linear relationship in fact. We denote this problem as having complexity O(N).

Sometimes, as the size of the input - N - increases, the complexity increases in different ways. For example, given a list of N cities and determining the shortest route to get round them all means that we have to try each possible permutation and then see which is the smallest. The number of permutations of visiting N cities is N factorial or N! so we say that this problem has complexity O(N!)

Likewise, if we are trying to guess someone's Facebook password by brute force (ie literally trying every possible password in turn until we hit the right one) then if the password is N bits long when expressed in binary then, given that each bit can be either 0 or 1 means that the complexity of cracking an N bit password is O(2^N) - ie increasing the password length by one bit makes it twice as hard to crack as before.

Some algorithms take longer to implement as the input size grows, but the impact id not so severe. Without going into detail (this is an introduction after all!) sorting a data set into order (eg the so-called Binary Search) depends logarithmically on the size of the input so we say this kind of algorithm has complexity O(logN).

There are many more types, and if this article has intrigued you to know more, take a look at https://en.wikipedia.org/wiki/Big_O_notation which covers things in more depth.

However, if you've understood this very brief introduction, then congratulations! As Roy Orbison, the Big O himself would have sung in his 1989 hit - "You've Got It!"