Big O Notation Explained
First in a series breaking on Big O Notation. First, let's explore what it is and why it'll make you a better engineer. Next up, O(1).
Anyone with a bit of experience in software engineering would be familiar with Hashes (also called Associative Arrays, Hash Maps, Maps, or Plain JavaScript Objects) and Arrays. These are called Data Structures, both of which have functions that manipulate the data they hold. Methods like filter, find or forEach on the Array or keys, entires or has on the Map.
Big O notation gives us a common language to describe how quickly these methods run, or how much space they take up in memory or on our hard drives. This allows us to speak to other software engineers and immediately understand the complexity, benefits, or drawbacks of certain methods, functions, or algorithms. Further, knowing and applying Big O notation correctly will help you stand out in interviews by demonstrating your ability to get an immediate understanding of a problem.
What is Big O Notation?
Anyone who knows me knows that I’m not a huge fan of needlessly complex software jargon. I find it needlessly gatekeeps concepts and ultimately leaves the entire software industry worse. In saying that, Big O is based on mathematics. As such, I’ll do my best to explain it in plain English.
Big O Notation comes in a few different flavors. I tend to think of these in terms of levels of difficulty, but the most often used ones are:
O(1) – This represents something that is constant, no matter how large the input is. Example: Accessing a specific array element.
O(n) – This represents something that grows linearly depending on the input. Example: looping through each element in an array. The more elements in the array (represented by n), the longer it’ll take.
O(log n) – The log stands for logarithmic time, where performance increases start off poor but gets better over time. Example: Binary search.
Big O notation gives us a common language to describe how quick these methods run, or how much space that take up in memory or on our harddrives. This allows us to speak to other software engineers and immediately understand the complexity, benefits or drawbacks of certain methods, functions or algorithms. Further, knowing and applying Big O notation correctly will help you stand out in interviewing by demonstrating your ability to get an immediate understanding of a problem.
Big O Notation in Interviews
Over 13 years in software engineering, I’ve only ever been asked to explain the Big O complexity of a function twice. In Australia at least, you’re more likely to get asked these types of questions from large companies (Byte Dance, Atlassian, Google, etc.). Smaller startups, or companies that put less emphasis on academics, are unlikely to ask you these questions.
Nevertheless, being able to discuss the Big O complexity of your approach shows that you can think critically about performance trade-offs.
Preparing for Big O Questions
When preparing for interviews, focus on:
Common Patterns: Recognize common algorithmic approaches and their typical Big O efficiencies.
Problem Breakdown: Practice breaking down problems to determine what kind of operations are involved and estimating their complexity.
Optimization: Learn how to improve inefficient solutions through better algorithm choices or data structures.
By mastering these elements, you will approach your interviews with a toolkit that allows you to articulate your solutions clearly and demonstrate your capability in handling real-world software challenges.
Wrapping it up
Engaging with Big O notation won't only improve your coding; it also enhances your overall analytical thinking, making you a more proficient developer and a standout candidate in technical interviews.
Want to dive deeper? Checkout my upcoming post breaking down O(1) complexity