Job Interview Dilemma
This is essentially the question that I received from a fellow podcast listener.
This person encountered this question during a job interview where they were asked how they would determine which of 5 balls were the heaviest if they were only given a scale that only tells you relative weight.
Once this fellow podcast listener gave their solution, the interviewers asked which algorithm their solution used… and they had no idea.
What the Heck are Algorithms?
An algorithm is essentially a well defined set of instructions that get carried out by a computer in an automated fashion to solve a problem. A good example of this is to say “How would you tell a computer to figure out which of the 5 balls I've given to you is the heaviest (or lightest)”. In order to solve this “problem”, you'll need to define a set of steps for the computer to carry out in order to reach a conclusion and solve the problem.
Algorithms are very common in programming, as you are constantly trying to tell the computer how to solve problems in a step by step manner.
Why do we care about Algorithms?
Well, without algorithms we likely wouldn't be able to solve some of the fundamental problems that we face when designing and creating software applications.
For example, how do you think it is that you're able to type in a search term like “Java Tutorials” into Google and have it spit out a massive list of websites that will solve your problem of wanting to learn Java? It's an algorithm!
So you should absolutely care about algorithms as they are a necessary evil to solving problems with computer programming… however, it's not just algorithms you should care about, it's also the speed of your algorithms that you should focus on.
What is Big-O Notation?
The Big-O Notation is the way we determine how fast any given algorithm is when put through its paces.
Consider this scenario: You are typing a search term into Google like “How to Program with Java” or “Java Video Tutorials”, you hit search, and you need to wait about 30 seconds before all of the results are on the screen and ready to go… Would you still use Google? Or would you start shopping around with other search engines to find one that is faster? My guess is you'd start shopping around.
Speed is everything these days, and building slow software is infuriating to users even if they aren't even paying for the software.
Being able to know how fast your algorithms are is the starting block to improving them and making your software faster. So the question is, “How do I know if my algorithms are fast or slow?”. Well, the Big-O Notation allows us to give a label to the speed of our algorithms.
The key to understanding the labels that go along with the Big-O Notation is to understand how the speed of an algorithm is calculated:
Operations per Element
What this means is essentially this: How much longer will your algorithm take to come to completion as the size/complexity of the system grows.
Examples
How long does it take for you to traverse a List from start to finish?
The answer? It depends!
If you only have 1 element in your List, the traversal of the List will be done after 1 operation. If you have 10 elements in your List, the traversal of the List will be done in 10 operations. If you have 1,000,000 elements in your List, it will be done in 1,000,000 operations.
You see how the number of operations grows linearly with the number of elements in the List?
This kind of algorithmic complexity is known as “linear”. The Big-O Notation for linear complexity is O(n)
How long would it take you to send an email to the friends of all of your friends?
Let's assume that we have a List of friends stored in our system. And each one of our friends has a List of their friends. How long would it take to email all of the friends of your friends?
Well let's think about it in terms of an algorithm! We'll have to traverse our List of friends to get access to their friends right? Okay. But then we'll also have to send an email to each of the those people, so we'd have to traverse the List of our friends' friends.
In programming code it may look like this:
for (Friend myFriend : myFriends)
{
for (Friend myFriendsFriend : myFriend.getFriends())
{
sendEmail(myFriendsFriend.getEmailAddress());
}
}
This code doesn't account for any special cases like “Do not email the same person twice”, but that sort of level of detail is not what I'm going for here. The key is, what is the complexity of this code compared to the other example we looked at where we just needed to traverse one list?
Well, it's all about numbers here… let's assume that you have 10 friends, and each of your friends has 10 friends. That would mean that you would need to execute 100 operations (or send 100 emails) in order to complete this task.
Okay, so what if you had 100 friends, and each of your friends had 100 friends? How long would it take to email them all? Well it would be completed in (100 * 100 = 1,000) operations. So even though you only have two lists which are each 100 elements in length, you may have though it would take 200 operations to complete this task, it actually takes many more operations.
So the complexity of this algorithm is quadratic, which in Big-O Notation is O(n2)
What are all of the Big-O Notations?
There are quite a few of them, Wiki has 12 different notations defined, if you're interested in seeing them all you can click on the Wiki page link at the bottom of this post. But for the sake of keeping you sane, I'll just list the popular ones:
| Speed | Notation | Name | Example |
|---|---|---|---|
| Fastest | O(1) | Constant | Determining if a number is even or odd; using a constant-size lookup table |
| O(log n) | Logarithmic | Finding an item in a sorted array with a binary search | |
| O(n) | Linear | Finding an item in an unsorted list | |
| O(n2) | Quadratic | Bubble Sort (worst case or naive implementation) | |
| Slowest | O(n!) | Factorial | Solving the traveling salesman problem via brute-force search |
Links Mentioned in this Episode
- http://bigocheatsheet.com/
- http://en.wikipedia.org/wiki/Big_O_notation