#Big O notation
##Learning Objectives
- understand what big O notation is
- understand examples of
- O(1)
- O(n)
- O(n^2)
- O(log n)
###What is Big O notation? Heres the formal definition, taken from wikipedia
let
f(x)andg(x)be 2 functions defined on some subset of real numbers, One writes(f)x = O(g(x)) as x -> ∞if and only if there is a positive constant M such that for all sufficiently large values of x, f(x) is at most M multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that|f(x)| <= M(g(x)| for all x > x0
Thats pretty dense, lets graph it out two functions and see how it works out
lets try graphing these two functions
f(x) = x**2 + 20x
g(x) = 10x
As they travel towards infinity we see that they the only term that affects the output in any meaningful way is x**2 in the first one, and x in the second.
Using Big O notation we would say the first equation is O(n**2) and the second is O(n)
In simple terms: Big-O notation is a relative representation of the complexity of an function/algorithm
I saw a great example of this on stack overflow: Imagine that you're trying to dry a bunch of shirts using a washing line outdoors. (assume you have an infinite backyard)
-
How long will it take to dry one shirt?
-
How about 5 shirts?
-
What about a million shirts?
No matter how many shirts you put out they will all get the same sun and fresh air!
As you put out infinite shirts, the dry time will stay the same!
What would this look like in Big O notation?
###Addition
The best example of Big-O I can think of is doing arithmetic. Take two numbers (123456 and 789012). The basic arithmetic operations we learnt in school were:
- addition
- subraction
- multiplication
- division
Each of these is an operation or a problem. How you solve it is an algorithm Lets start with addition, if you wanted to add together 2 5 digit numbers how many operations would you have to do?
Now what if we had two 100 digit numbers? 10,000 digit numbers? 10 million digit numbers?
The complexity(the number of operations) is directly proportional to the number of digits
Any clues on how this would be using big O notation?
O(n) or what we call linear complexity
###Multiplication
Lets take the case of multiplication, if I multiply two 3 digit numbers, say 350 by 200 how many operations do I need to perform?
Have a partner count the amount of times you multiply and add and lets see what you come up with.
9 multiplications and 1 addition
Now switch and you count for your partner as you multiply 21 * 15.
what if I multiply 21 * 15? 4 multiplications and 3 additions right?
Now take some time and talk it over with your partner and figure this part out:
What is the maximum operations that I would need to do to multiply two 10 digit numbers?
How could we right this in equation form to find out the amount of operations to multiple two numbers given the number of digits?
You may notice that we assume the worst case scenario here, thats what we have to do when calculating big O notation.
Remember we only care about the most significant portion of the operation as it tends towards infinity, knowing this, what is the big O notation for multiplication?
This is a classic example from CS courses that people use.
Does anyone remember back in the day there used to be white pages? It would be a book that had everyone in it like:
- Last Name, First Name Address Phone Number
Lets assume that we are looking for someone named John Smith in a phone book of a thousand names, work with your partner and try to thinkof the most efficient strategy for finding this person.
remember, we want the solution that has the least amount of operations
What solution did you guys come up with?
How long would it take if the phone book had a million (1,000 * 1,000) names?
So how does the complexity of this function increase as the number of inputs increases?
- its definitely not set as in
o(1) - its not linear, we increased the inputs by a thousand-fold, and our time didnt increase by that much.
- is it quadratic?
- whats left?
- Might have to remember your high school math for this one....
###Traveling Salesman This is another classic CS problem to illustrate the last level of complexity that you're likely to encounter.
A traveling salesman needs to travel around a bunch of interconnected towns. Given towns A, B, C work with a partner and figure out the different ways to go through each and every town.
Once you've got all the possible paths written out, cross off the ones that follow the same roads, just in reverse.
How many possibilities did you get?
Now add another town into the Mix so we have towns A, B, C, and D and do the same thing. what would happen if we added in a 5th town? or a sixth? how many possibilites would there be?
This level of complexity is called factorial complexity or O(n!)
###Conclusion
You will see the words Big O notation pop up in your career as developers from time to time, and I dont want you all to be stunned, the concepts can be tough to grasp but sometimes it just takes the right analogy and things instantly become clear. Luckily, there are tons of good analogies on the internet :).
If you notice, I havent explained any of this using javascript or ruby, these concepts are language agnostic they are always there just some languages hide it a little better than others.
I want you guys to have a good solid foundation in this stuff, in the afternoon today we're going to be writing Search and Sort algorithms and I want you all to be able to tell me what the big O notation for the different algorithms are after we write them out.