What computers can, and have always been capable of, is executing things incredibly quickly. So even if it uses repeated addition, it adds so quickly that you don't even feel it adds repeatedly, it just spits out the answer as if it used its memory like you would have.
However, fast as computers are, sometimes, you need it to be faster, and that's what we're going to tackle in this article.
But first, let's consider this:
Well, what we'd do is open the doors, and hope we're lucky to get the number.
Now suppose I give you a clue. This time, I tell you the numbers are sorted, from lowest to highest. You can instantly see that we can work on opening the doors more systematically:
In the worst case scenario, if we opened the doors wildly, or linearly, opening doors one by one without a care, we would have to open all doors to find what we are looking for.
In our new systematized approach, we would have to open a significantly lower number of doors - even in the worst case scenario.
This approach is logarithmic in running time, because we always divide our number of doors by half.
Here is a graph of the doors we have to open, relative to the number of doors.
See how much faster log n is, even on incredibly large input. On the worst case scenario, if we had 1000 doors and we opened them linearly, we would have to open all of them. If we leverage the fact that the numbers are sorted however, we could continually divide the problem in half, and drastically lower that number.
An Algorithm is a step by step procedure for solving a problem, and here we have two basic algorithms.
As you have already seen, our second algorithm is faster than our first in the worst case scenario. We could classify them by running time, the time it needs to take to complete the problem, which we equated here by the numbers of doors opened (since you take time to open doors).
The first algorithm, which is a linear search algorithm, would have to open ALL doors, so we say it's running time is O(n), (pronounced Big-Oh-of-n) where n is the number of doors (input).
The second algorithm, which is a binary search algorithm, would have to open a logarithmic amount of doors, so we say it's running time is O(log n).
In the so called O-Notation, O represents the time it needs to take for your algorithm to complete the task in the worst case scenario.
We haven't looked at the other side of the coin however. What about the best case scenario?
In both of our algorithms, the best case scenario would be to find the what we're looking for in the very first door of course! So, in both our cases, the best case running time would be 1. In O-Notation, theta (Ω) represents the best case scenario. So in notation, we say Ω(1)
Here is a table so far of our algorithms:
Sorting - Case StudyLet's say I'm making an RTS, and I needed to sort out units by their health.
A human being can sort this out very easily - one can instantly 'see' that it should be arranged like so:
In reality though, it actually does a series of steps, an algorithm, to sort out these pigs. Let's try to solve this problem programmatically.
One very straight forward way to solve this problem is walk through our input, and if they are not sorted, we swap them:
Are the first two pigs sorted? Yes, so we leave them be.
Are the next two pigs sorted?
We will continually do this recursively, until we walk through our input and see that we have in fact sorted it out.
To save you some bandwidth, here is our sorting algorithm in an animation, courtesy of Wikipedia:
(The animation is pretty long, so you might want to refresh the page to start over)
The algorithm we have described here is a Bubble Sort. Let's define it's running time shall we?
How many steps do we take to fully sort it out?
First we walk through our input. If our input is n, that is a total of n steps.
But how many times do we start over and walk again? Well, in the worst case scenario, that is, when the numbers are arranged largest to lowest, then we would have to walk through it n times too.
So n steps per walk, and n walks, then that is a total of n2.
In the best case scenario, we would only need to walk through it once (and see it's already sorted). In that case, n steps per walk, and 1 walk, then that is a total of n.
Now you might have noticed this, but n2 is a pretty bad number to have. If we had to sort 100 elements, then that means we have to take 1002 steps, that is 10,000 steps for a 100 elements!
Selection SortLet's use another approach. This time, we walk through the input left to right, keeping track of the smallest number we find.
After each walkthrough, we swap the smallest number with the leftmost one that is not in the correct place yet.
To again save you some bandwidth, here is an animation, again courtesy of Wikipedia:
But what is the running time?
In the worst case scenario, we would have to do n walks. The steps per walk decreases. Since we know that the first few numbers are already sorted, we can skip it. So our walks then become n, n-1, n-2... and so on.
The total running time of this is (n(n-1))/2. However, computers are so fast that a division is negligible, so we can say that this is n2 still.
But what about the best case scenario? If you think about it, we would still need to walk through the input, even if it is already arranged! So our best case scenario is also n2.
Insertion sortOkay, so all of our examples so far has been n2 which we know is bad. Let's take a look at another algorithm shall we?
Imagine you're sorting a deck of cards. Now I don't know about you, but most would do is walk through the deck, and insert the card in front of them to its right position in another deck.
This might help you visualize it:
Not quite. What if we needed to insert 1 to our sorted list? We would have to move every single one of them to make room. If you consider this, the worst case running time is actually n2.
Let's table them shall we:
You might want to take a look at this visualization to see just how fast merge sort is to bubble, selection, and insertion sorts.
Note: That little tidbit about computers doing repeated addition is a bit of a lie.
Credits- Running Time Graph Image taken from: CS50, taught by David J. Malan from Harvard University
- Visualization Animations from Wikipedia.