You want to know all there is to know of big O? So do I.
So to talk of big O, I will use words that have just one beat in them. One sound per word. Small words are quick. You know these words, and so do I. We will use words with one sound. They are small. I am sure you will know all of the words we will use!
Now, let’s you and me talk of work. Most of the time, I do not like work. Do you like work? It may be the case that you do, but I am sure I do not.
I do not like to go to work. I do not like to spend time at work. If I had my way, I would like just to play, and do fun things. Do you feel the same as I do?
Now at times, I do have to go to work. It is sad, but true. So, when I am at work, I have a rule: I try to do less work. As near to no work as I can. Then I go play!
So here is the big news: the big O can help me not to do work! I can play more of the time, if I know big O. Less work, more play! That is what big O helps me do.
Now I have some work. I have this list: one, two, three, four, five, six. I must add all things in this list.
Wow, I hate work. But oh well, I have to do this. So here I go.
One plus two is three… plus three is six... and four is... I don’t know. I got lost. It is too hard for me to do in my head. I don’t much care for this kind of work.
So let's not do the work. Let's you and me just think how hard it is. How much work would I have to do, to add six numbers?
Well, let’s see. I must add one and two, and then add that to three, and then add that to four… All in all, I count six adds. I have to do six adds to solve this.
Here comes big O, to tell us just how hard this math is.
Big O says: we must do six adds to solve this. One add, for each thing from one to six. Six small bits of work... each bit of work is one add.
Well, I will not do the work to add them now. But I know how hard it would be. It would be six adds.
Oh no, now I have more work. Sheesh. Who makes this kind of stuff?!
Now they ask me to add from one to ten! Why would I do that? I did not want to add one to six. To add from one to ten… well… that would be even more hard!
How much more hard would it be? How much more work would I have to do? Do I need more or less steps?
Well, I guess I would have to do ten adds… one for each thing from one to ten. Ten is more than six. I would have to work that much more to add from one to ten, than one to six!
I do not want to add right now. I just want to think on how hard it might be to add that much. And, I hope, to play as soon as I can.
To add from one to six, that is some work. But do you see, to add from one to ten, that is more work?
Big O is your friend and mine. Big O helps us think on how much work we have to do, so we can plan. And, if we are friends with big O, he can help us choose work that is not so hard!
Now we must do new work. Oh, no. I don’t like this work thing at all.
The new work is: add all things from one to n.
Wait! What is n? Did I miss that? How can I add from one to n if you don’t tell me what n is?
Well, I don’t know what n is. I was not told. Were you? No? Oh well. So we can’t do the work. Whew.
But though we will not do the work now, we can guess how hard it would be, if we knew n. We would have to add up n things, right? Of course!
Now here comes big O, and he will tell us how hard this work is. He says: to add all things from one to N, one by one, is O(n). To add all these things, [I know I must add n times.] That is big O! He tells us how hard it is to do some type of work.
To me, I think of big O like a big, slow, boss man. He thinks on work, but he does not do it. He might say, "That work is quick." Or, he might say, "That work is so slow and hard!" But he does not do the work. He just looks at the work, and then he tells us how much time it might take.
I care lots for big O. Why? I do not like to work! No one likes to work. That is why we all love big O! He tells us how fast we can work. He helps us think of how hard work is.
Uh oh, more work. Now, let’s not do the work. But, let’s make a plan to do it, step by step.
They gave us a deck of ten cards. They are all mixed up: seven, four, two, six… not straight at all. And now... our job is to sort them.
Ergh. That sounds like a lot of work!
How can we sort this deck? I have a plan.
I will look at each pair of cards, pair by pair, through the deck, from first to last. If the first card in one pair is big and the next card in that pair is small, I swap them. Else, I go to the next pair, and so on and so on... and soon, the deck is done.
When the deck is done, I ask: did I swap cards in that pass? If so, I must do it all once more, from the top.
At some point, at some time, there will be no swaps, and our sort of the deck would be done. So much work!
Well, how much work would that be, to sort the cards with those rules?
I have ten cards. And, most of the time -- that is, if I don’t have lots of luck -- I must go through the whole deck up to ten times, with up to ten card swaps each time through the deck.
Big O, help me!
Big O comes in and says: for a deck of n cards, to sort it this way will be done in O(N squared) time.
Why does he say n squared?
Well, you know n squared is n times n. Now, I get it: n cards checked, up to what might be n times through the deck. That is two loops, each with n steps. That is n squared much work to be done. A lot of work, for sure!
Now when big O says it will take O(n squared) work, he does not mean n squared adds, on the nose. It might be some small bit less, for some case. But in the worst case, it will be near n squared steps of work to sort the deck.
Now here is where big O is our friend.
Big O points out this: as n gets big, when we sort cards, the job gets MUCH MUCH MORE HARD than the old just-add-these-things job. How do we know this?
Well, if n gets real big, we do not care what we might add to n or n squared.
For big n, n squared is more large than n.
Big O tells us that to sort things is more hard than to add things. O(n squared) is more than O(n) for big n. That means: if n gets real big, to sort a mixed deck of n things MUST take more time, than to just add n mixed things.
Big O does not solve the work for us. Big O tells us how hard the work is.
I have a deck of cards. I did sort them. You helped. Thanks.
Is there a more fast way to sort the cards? Can big O help us?
Yes, there is a more fast way! It takes some time to learn, but it works... and it works quite fast. You can try it too, but take your time with each step and do not lose your place.
In this new way to sort a deck, we do not check pairs of cards the way we did a while ago. Here are your new rules to sort this deck:
One: I choose one card in the part of the deck we work on now. You can choose one for me if you like. (The first time we do this, “the part of the deck we work on now” is the whole deck, of course.)
Two: I splay the deck on that card you chose. What is this splay; how do I splay? Well, I go from the start card down, one by one, and I look for a card that is more high than the splay card.
Three: I go from the end card up, and I look for a card that is more low than the splay card.
Once I have found these two cards, I swap them, and go on to look for more cards to swap. That is, I go back to step Two, and splay on the card you chose some more.
At some point, this loop (from Two to Three) will end. It ends when both halves of this search meet at the splay card. Then, we have just splayed the deck with the card you chose in step One. Now, all the cards near the start are more low than the splay card; and the cards near the end are more high than the splay card. Cool trick!
Four (and this is the fun part): I have two small decks now, one more low than the splay card, and one more high. Now I go to step one, on each small deck! That is to say, I start from step One on the first small deck, and when that work is done, I start from step One on the next small deck.
I break up the deck in parts, and sort each part, more small and more small, and at some time I have no more work to do. Now this may seem slow, with all the rules. But trust me, it is not slow at all. It is much less work than the first way to sort things!
What is this sort called? It is called Quick Sort! That sort was made by a man called C. A. R. Hoare and he called it Quick Sort. Now, Quick Sort gets used all the time!
Quick Sort breaks up big decks in small ones. That is to say, it breaks up big tasks in small ones.
Hmmm. There may be a rule in there, I think. To make big tasks small, break them up.
This sort is quite quick. How quick? Big O tells us: this sort needs O(n log n) work to be done, in the mean case.
Is it more or less fast than the first sort? Big O, please help!
The first sort was O(n squared). But Quick Sort is O(n log n). You know that n log n is less than n squared, for big n, right? Well, that is how we know that Quick Sort is fast!
If you have to sort a deck, what is the best way? Well, you can do what you want, but I would choose Quick Sort.
Why do I choose Quick Sort? I do not like to work, of course! I want work done as soon as I can get it done.
How do I know Quick Sort is less work? I know that O(n log n) is less than O(n squared). The O's are more small, so Quick Sort is less work!
Now you know my friend, Big O. He helps us do less work. And if you know big O, you can do less work too!
You learned all that with me! You are so smart! Thank you so much!
Now that work is done, let’s go play!
: There is a way to cheat and add all the things from one to n, all at one time. Some kid named Gauss found this out when he was eight. I am not that smart though, so don't ask me how he did it.