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²): 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
Our interactive course Big O Notation For Coding Interviews & Beyond is a simple and practical guide to algorithmic complexity. Learn what you need to know specifically to analyze any algorithm, and ace your next coding interview.
This course 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.
The course features plenty of live code snippets so you can see how Big-O can be applied to real software algorithms. And each chapter ends with an interactive quiz to test your knowledge every step of the way.
By the time you wrap up this course, you’ll have a working knowledge of Big-O, and the confidence to ace your programming interview at any tech company!
Be fully prepared for your next coding interview with Big O Notation For Coding Interviews & Beyond on Educative — the learning platform for software developers.
Bonus: Some other interview prep resources
Big-O Notation For Coding Interviews & Beyond is an addition to our long series of best-selling interview preparation courses on Educative. Designed by hiring managers at Microsoft, Facebook, Amazon, and Uber, these courses give you an inside look at what you’re likely to be asked at a major tech company interview.
Get some extra practice with these popular interview prep courses:
Originally published at blog.educative.io on December 26, 2018.