Breaking Down Big O Notation
There comes a point as a self taught developer or a bootcamp grad that you start hearing words like runtime and efficiency. You begin to edit your resume, start studying, and the first thing you come across is Big O.This blog post will break down concepts that are necessary for you to know as you prep for algorithms.
Big O is the language we use for talking about how long an algorithm takes to run. It’s how efficiency is compared to a problem.
Big O notation is referring to how quickly it grows relative to the input, as the input gets arbitrarily large.
What does that mean 👀 :
- how quickly the runtime grows — it’s hard to say “exactly” the runtime of an algorithm. The speed of the processor is in play, what else is running, etc. So Big O is used to measure how quickly the runtime grows.
- relative to the input — measuring runtime directly could allow us to refer to the speed in seconds. However we are measuring its growth. So “n” is what we refer to for the input and when we refer to “the order of the size of the input” we mean O(n) or O(n²).
- as the input gets arbitrarily large — we care about what grows the fastest and the input grows. So if you have O(n² + 1) runtime, it’s actually O(n²) because the 1 is arbitrary in terms of size and small in comparing to something growing exponentially. *however sometimes the constants matter📝*
Examples of Big O
This function runs in O(1) time or constant time relative to its input. The input array could be 1 item or 1,000 items. But this function just needs one “step”.
This function runs in O(n) time or linear time where n is the number of items in the array. If there are 5 things in the array, we print it 5 times. If there are 100 things in the array, we print it 100 times.
Here we have a nested loops 🧐. If the array has n items that means the outer loop runs n times. Then our inner loop runs n times for each iteration of the outer loop. This is O(n²) or quadratic time. If there are 10 items in the array, it is being printed 100 times. (10² = 100). Going back to our chart at the top of the page, this is a horrible runtime.
You can also view that chart here .
Why is it important?
When you care about building your product, app, feature, etc in a fast manner you may not really care about Big O analysis. You want to get it done. However you want to strike a balance. It’s all about writing intentional code. If your product/features ships the fastest within a deadline — that’s great. But what happens when you need that feature to grow for 10 users, 100, 1,000, or 10,000. Will your code be able to grow and handle runtime, space, implementation, maintainability, and readability?
Conclusion
This will take practice to understand. Be patient with yourself as you learn new algorithms for interviews. The more you see it, read it, and write it… the clearer the patterns for Big O are. Let me know what other questions you have about Big O for future blogs and what resources you are currently using! ✨
✨Honorable mention to Annie#algo-club✨
