You didn’t think I was going to stop beating that programming interview concepts post into the ground, did you? Unlike some of the other concepts, big O notation is something you actually need to understand to write good code. Even better, you don’t need to know the term big O notation to have a conversation about the underlying concept.
Big O notation, also known as the order of a function, is a way of describing how much worse a function performs when you give it more input. If you’re sorting a small enough list, for example, it really doesn’t matter how efficient your algorithm is. If your list is a million items long, then the efficiency of your algorithm suddenly matters a whole lot.
The specifics aren’t necessarily that interesting, but let’s run through them quickly. Some functions, like figuring out whether a number is even or odd, are constant, or O(1). No matter how big a number you give that function, it’s going to take about the same amount of time to figure out whether it’s even. Functions that take longer in direct proportion to the size of the input, like finding an item in an unsorted list are called O(n) – the order is the same as the size of the input. Inefficient sort algorithms like insertion sort or bubble sort get much worse, O(n²). A bad sort has to compare each item in the list to every item in the list, which means that performance gets worse much faster than the input size increases. An extremely inefficient algorithm could even be O(n!), for example brute-forcing the travelling salesman problem.
In other words, nested loops are really, really bad :)
Understanding just how much worse an inefficient algorithm performs is a really important part of being able to make reasonable tradeoffs in your code. If your input is large enough, creating a binary tree out of it may be worth the extra memory usage for the improvement in time to find any given item. Assuming the computer will just magically handle it is not good enough when you may have to process hundreds of thousands of items or more.
As an interview question, I actually like big O notation – as long as you don’t insist on using those exact words to describe it. There’s no reason you need to use comp sci jargon to talk about which function of two examples would perform better with a massive amount of data to work on. It’s also something you can have an actual conversation about. Sometimes an inefficient algorithm is your only option, sometimes it can be avoided by using a different data structure, sometimes you can avoid the issue entirely by finding a different way to meet the user’s needs. That much more interesting to talk about than whether your candidate thought to look up how a breadth first search works :)
1 Comment
How does binary search work, anyway? – Mel Reams
[…] to wikipedia a binary search makes at worst O(log2 n) comparisons, which is pretty great when you have a large array. Because the search halves the […]