Math is programming. Programming is math.
For millions of self-taught programmers who don’t necessarily like math, this is an inconvenient truth you’ll need to deal with. Mathematical logic is the core of all programming. Most of its methods and concepts are entirely based on what you learned in math class.
Nowhere is the connection between math and programming more evident than algorithms.
Big-O notation: A simple explanation
If a computer program is like a meal with several ingredients, the algorithm is the recipe. It shows you the ingredients (or “inputs”) and all the steps it will take (or the “procedure”) to put your meal (or “output”) together.
And depending on the complexity of your recipe, some algorithms won’t run very efficiently as you continue to add more steps.
Big-O notation is a mathematical function used to describe how complex an algorithm is — or more specifically, the execution time required by an algorithm.
Programmers use Big-O to compare multiple algorithmic approaches so they can choose the one that makes the most sense.
It does this by presenting a “worst-case” scenario of how long it would take an algorithm to run (or in math terms, it puts an “asymptotic upper bound” on the time it takes an algorithm to run).
Of course, it’s not absolute mathematical proof, but it gives you enough of an idea to make an informed decision.
This becomes really important when you scale an app or website. When you’re dealing with requests from millions of users, the time it takes to handle those requests is crucial. Or if you have an app that works with lots of data, you’ll need to know how to handle it so the app can run as efficiently as possible.
Common varieties of Big-O notation
These varieties of Big-O notation aren’t the only ones, but they’re the ones you’re most likely to encounter.
O(1): Your algorithm will run the same, regardless of how many elements are in your list.
O(log n): The time it takes for your algorithm to run will plateau, no matter how many elements are in your list.
O(n): As the elements in your list increase, the more time it will take for your algorithm to run.
O(n^2 ): As the elements in your list increase, the time it will take for your algorithm to run will increase exponentially.
Do you really need to know this stuff?
If you’re dealing with, say, a sorting algorithm, you might ask yourself, “aren’t there sort functions that do what Big-O does?”
Sure. But you’ll want to calculate an algorithm’s efficiency, MINUS all the variables presented by a computer program (like the hardware, or the OS). If you have a grasp of Big-O notation, you can design algorithms for efficiency — and save your self a lot of potential headache.
Big-O also comes in handy when you’re trying to create a composite of multiple algorithms, or have to tie pieces together. Plus, Big-O just happens to be a subject that hiring managers love to bring up in coding interviews.
Why Big-O Notation comes up a lot in coding interviews
Software companies are concerned with scalability. If you can scale your software, you can scale your revenue.
Hiring managers will certainly ask you questions about Big-O if you’re involved in software design, because they want to know how you’ll handle the inevitable scaling issues.
Also, by showing a good grasp of Big-O, you’ll prove yourself as a candidate who has a fundamental understanding of programming — and the math that powers it.
Be prepared for Big-O notation questions
There are a lot of great resources out there for people who want to learn how to implement Big-O notation. I recommend an interactive course, because hands-on practice is important when dealing with abstract concepts and algorithms. Try to root your learning in actual real-world examples and implementations, or else the information won't stick.
One resource is the interactive course Big O For Coding Interviews & Beyond, which is a simple and practical guide to algorithmic complexity. It is designed for folks who aren’t math whizzes, or even super-experienced in programming. Written in a conversational style, chock full of real-world examples, this course is an antidote to the mountains of dry, technical Big-O reference. Since it is aimed for interview prep, you'll also be empowering your career as you learn.
Some other resources
- Khan Academy Big-O Notation
- Rob Bell's Beginner Guide
- Big-O notation: definition and examples
- Free Code Camp Big-O Notation
- Sarah Chima's article (check out her account here)
Happy learning!
Top comments (0)