.O
“The Big O” or How I Learned to Love Runtime Complexity.
I graduated from Flatiron School’s program recently, and I was shocked and horrified to find out that this seemingly essential piece of knowledge was left by the cerebral wayside. Why haven’t we met? Is it something I said? Do you think its because I wasn’t ready? That’s… that very well could be true.
When you’re in bootcamp, the focus is to get the job done by any means necessary, no matter how messy or inefficient the code. A “by the skin of your teeth” experience that warranted such oversights and shortcuts. These are small applications and would never even feel the icy touch of O(2^n).
While burying my head in Udemy courses on algorithms(rhythms), data structures and said aforementioned elephant in the room, I thought I might enlighten you on a few things I learned with a birds-eye view of That SpecTACular O!
Constant Time( 1 )
The holy grail! This is essentially saying that, no matter how much you double down your data, the operation will always take the same amount of time.
Logarithmic Time( log(n) )
This is an indication that doubling the amount of elements available doesn’t double the workload. Its very typical for search functions to be log(n)
Linear Time( n )
This is typical when iterating through all elements in a particular collection. A good example is a for loop that indicates a span (ex. 0 to arr.length) will typically evaluate to n.
Quasilinear Time( n * log(n) )
This follows the rules log(n), but is typically found when implementing a sort function.
Quadratic Time( n² )
Things are starting to bog down just a little bit. We’re at the penultimate stop here, and this is when every element needs to be compared to every other. You’ll typically see n² when dealing with a nested for loop over the same collection.
Exponential Time( 2^n )
You really stuck your foot in it now. This means if you add a single element to a collection, the amount of resources needed doubles. Woof.
As I continue my journey down the path of enlightenment, I’ll be sure to keep you posted. Understanding algorithms and data structures is absolutely essential study to get the job of your dreams. Just don’t be surprised if after you perfect coding of “FizzBuzz”the interviewer asks “What is the runtime complexity of your algorithm?” (It’s 42)