Find Your Best Code Solution Understanding Big 0 Notation
Big 0 notation is an essential concept to understand for your developer’s career. First, it is asked a lot in coding interviews questions. Second, it’s the determining factor when it comes to choosing your most efficient code solution or algorithm.
I already mentioned in another article how code changes when implemented on a large scale. Suppose you write a function that gets a series of strings and then parses out some word out of them.
For most of you, such a program would be a no-brainer to implement in your language of choice. But what happens if the input strings start to become 10000? Or maybe a million, or even ten million.
You would still have 10 ways of doing it with all the tools that modern languages offer. But what’s the actual best way? What is the solution that takes up less runtime? Or in other words, what’s the most efficient algorithm?
That’s when Big 0 notation comes in handy.
Big 0 is your language of choice to express the complexity of your algorithms. Or, in simplified words, Big 0 is the way you will use to describe the runtime of your solution in terms of how quickly it grows relative to the input, as the input gets arbitrarily large.
It’s practical terms, it just boils down to some easy math formula, but without all the math hard stuff and with a lot of abstraction. In fact, Big 0 provides you with three different levels of abstraction:
-
It’s hard to determine the exact runtime of an algorithm. Since this is tied to the processor running it, what else the computer is running and sometimes even the browser used can mislead the final result. Big 0 addresses this issue by describing just how quickly the runtime grows.
-
Since we’re not using time constraints to measure the efficiency of our algorithms, Big 0 has to introduce another abstraction to describe the incremental runtime. The size of the input, called n, is used for this purpose. So you will often see stuff like: “This runtime grows in the order of the size of the input O(n)”.
-
Your algorithms may have parts that could look expensive at first. But they will become totally irrelevant as n will grow. That’s why you will never see stuff like 0(n +1).
Practical Examples
In this function, you can see that we always perform the same operation: returning the first element of the passed-in array. It doesn’t matter how many items such array will contain. The runtime will be constant, or better expressed as O(1).
In this example, you can see how, as n grows, the runtime will grow. If you have 10 items, you will have to console.log 10 times, if n is 10000 you will have to log 10000 times and so on. So this function runs in what’s called linear time O(n).
This is an algorithm whose performance is directly proportional to the square of the size of the input data set: O(n²). This is pretty common with nested loops, which should generally be avoided as a rule of thumb. Note how more nested loops can also bring to a situation where you have 0(n³) 0(n⁴).
Simplifying Big 0 Expressions
As mentioned above, never forget to simplify your big 0 expressions, as you just need to express the most important data. In fact, some steps of your algorithm may look important to you, but as n grows they will become totally useless to mention.
Instead of expressing constants, always use O(1):
0(500) becomes O(1)For incredibly big numbers like 1000000, added numbers don’t matter, so:
0(n + 1) becomes O(n); ------------ O(2n) becomes O(n) Think about it, is it really important to specify that 1 when you’re dealing with a giant input? Is that really meaningful information?
Space Complexity
Sometimes, instead of calculating runtime, you may wish to calculate memory usage. Big 0 comes in handy also in this case. The usage is similar to that of runtime, you simply look the total size (relative to the size of the input) of any new variables you’re allocating.
In this case, since you’re just allocating one variable i, you have a constant memory usage, or better O(1).
While in the following example, since the size of your array will scale with the number of elements passed as input n, we say that the memory usage is linear, or better O(n).
Keep in mind that when it comes to space complexity, space created by the passed in inputs is not taken into consideration.
Conclusion
Big O is one of those tools that every developer needs. And it’s something that true professionals have hardwired in their brains in order to find the best possible solution. So make Big O one of your best friends, and watch your code get better and better!
Key Takeaways
- Big 0 is an extremely important tool, both for acing code interview and building better algorithms.
- Big 0 is the way you will use to describe the runtime of your solution in terms of how quickly it grows relative to the input, as the input gets arbitrarily large.
- It can be used both to determine runtime and space complexity.
- True professionals know how to use Big O to find a balance between runtime, memory usage and complexity of a solution.
Resources
Open Source Session Replay
OpenReplay is an open-source, session replay suite that lets you see what users do on your web app, helping you troubleshoot issues faster. OpenReplay is self-hosted for full control over your data.
Start enjoying your debugging experience - start using OpenReplay for free.