Not really.
Your input could be 2 letters or it could be twelve billion.
It could be running on an old laptop or a super computer and take a very different amount of time to run.
If the program is adding each number to itself three times instead of two, it will still be O(n) because even though your program is doing more operations per input, how much more is constant per input.
O(n) is a decent time complexity and you often can’t avoid it.
Order n squared or O(n²)Now say you want your program to add every member of the list to each other.
[a,b,c,d,e] => [abcde, bacde, cabde, dabce, eabcd]Since for each item in the list you have to also go through the whole rest of the list, the number of operations your program has to do is the number of inputs (or n) times itself (n squared).
If your list has two letters in it, your program will take 4 operations to run.
If your list has four trillion letters, it may never finish running!O(n²) is almost never an acceptable time complexity and you can usually avoid it with a clever algorithm of some kind.
Logarithmic time or O(log n)matplotlib xkcd style graphs!Looking at this figure, you can see how each of the four runtimes scale.
Orange quadratic spikes up super fast while green constant stays the same no matter the input.
But what about that blue logarithmic line?.That looks almost as good as constant time!Logarithmsa quantity representing the power to which a fixed number (the base) must be raised to produce a given number.
If you haven’t thought about algebra since high school, you’ll want a refresher on just what the heck a logarithm is.
Here Comes The MathLogarithms are used to solve for x when x is in the exponent.
Look at this equation:3^x == 9The question logarithms answer is “what power do we raise 3 to to get 9”.
The answer, of course, is 2!log3(9) == 2A logarithmic function is the opposite of an exponential function.
When you say something grows exponentially, it’s being multiplied.
When something grows logarithmically, it is being divided.
Look!.They’re mirrored.
That means that if you have 2 list items to go through and your program runs in log base 2 of n time, it will take one operation to execute.
That’s really powerful!.It will take fewer operations to run than you have data.
The bigger the input, the smaller proportion of the actual input your program has to go through!Logarithms in PracticeLooking at my list again:[a,b,c,d,e]If I want to search through it and find d for example, maybe you’ll write a program that looks at each letter in order and returns the index (3) when it finds what it is looking for (d).
That search will take four operations.
Not too bad right?.What if we were looking for e instead?.Only five operations.
Since that is the worst case scenario and five is the length of the input, that search algorithm will be O(n).
It’s fine for a small list, but if we were searching a list with a billion elements for the element at the very end, this algorithm would take a long time.
Flamenco SearchWhat if we could speed this up to O(log n)?.Well, if the list is sorted, we can!.I’ll let these flamenco dancers explain it:Notice how the dancers are in a line with numbers on their backs.
The man with the number 7 on his back is looking for the woman who matches.
He doesn’t know where she is but he knows all the ladies are in sorted order.
His process is to go to the dancer in the middle and ask her which side of her number 7 is on.
When she says “she’s to the left of me” he can rule out everyone to her right.
Next, he asks the woman in the middle of the left side the same question.
This lets him rule out another half of the candidates and so on until he finds number 7.
This program runs in O(log n) time because in the worst case scenario, the number of operations it takes to run will be log base 2 of the input size.
In this case, since there are 7 dancers in our ‘list’, the runtime is log2(7) or ~3 operations.
This algorithm is called a binary search because you narrow the search by two every operation.
It’s the poster child for O(log n).
Thanks for Reading!Hope that makes sense!.If something is unclear please leave a comment.
Cover photo by Ricardo Gomez Angel on Unsplash.