Big O Notation
So it turns out math is cool.
Big O notation is what I learned today in my coding assignments and I wanted to share it with you since teaching helps it stick.
Effectively what we are accomplishing with this notation is a description of the amount of resource consumption that a program will consume over time. Ideally we end up with O(1) but that won't be the case for everything so we need a way to describe growing demands in resources across time or iteration.
The notation goes as follows for what I understand in Python:
Constant O(1)
Logarithmic O(log n)
Linear O(n)
Squared O(n^2)
Exponential O(2^n)
Factorial O(n!)
What each of these notations is describing is the amount of operations a process will increase by, worst case, if scaled with 'n' inputs.
What's an example?
for i in range(6):
counter += 1
If we were to imagine that range allows any input of an integer we could see how this function only iterates once per input value giving it a LINEAR growth.
If we look at a number line this makes sense.
0-1-2-3-4-5-6
Our process starts at 0 and iterates once to get to 1 etc. until it eventually reaches 6. This is O(n).
If we added another layered loop:
for i in range (6): <- Loops what's below it 6 times.
for d in range(6): <- Loops what's below it 6 times.
counter += 1
We have now increased the processing demand QUADRATICALLY. Why? Because if we assume 6 to be the variable integer that we could influence we can see that by doing it twice we have to count to 6 uh.... 6 times.
0-6-12-18-24-30-36 <-
That's O(n^2). Now we have dramatically increased the amount of processes something requires with a SINGLE line of code.
Why is this important?
Well computers run things so fast that this 'lag' you could call it might build up over time. Memory leaks, mandatory resets, etc. are some results of this. The frequency at which this maintenance needs to be performed to keep the code functioning is directly connected to the 'Big O' notation used to determine how elegant the solution is.
Turns out different algorithms have varying Big O values which is how one might determine the best option for their given task.
It's also just a neat way to look at data but I'll wax poetic in logarithms once I have a more full understanding of them.
That's all for now!
