choong pw

As engineers, we all strive to build performant software. But how do we quantify performance? Enter Big O Notation, a mathematical concept that helps us analyze how an algorithm’s execution time scales with the size of its input.

It’s not just about bragging about the fastest code; Big O Notation is a powerful tool for making informed decisions about the algorithms we choose and the data structures we use. A simple chart to represent it all is something like this.

Let’s break it down:

• On one end, you have input that represents the data. By pure logic, the more data you have the longer it takes to process.
• On the other end, you have time complexity that shows the time taken to process the programming logic(algorithm).
• Lastly, the lines represent the algorithm in the form of time complexity against the growing input size.

Most of the algorithms tend to head towards infinity as the input size grows. Therefore, smartly designed algorithms can do wonders in saving computing memory and processing power. 

Common Big O complexities with example

• O(1): Constant time. The algorithm’s runtime is independent of the input size. Think of accessing an element in an array by index.
• O(n): Linear time. The runtime grows proportionally to the input size. Imagine iterating through a list, where each iteration takes constant time.
• O(n^2): Quadratic time. The runtime grows quadratically with the input size. Nested loops are a prime example.
• O(log n): Logarithmic time. The runtime increases logarithmically with the input size. Binary search is a classic example.

Practical applications

Now, let’s see Big O in action:

• Choosing a Sorting Algorithm:  Imagine sorting a massive dataset.  Bubble Sort (O(n^2)) might work for a small list, but for larger datasets, it becomes agonizingly slow.  Meanwhile, Merge Sort (O(n log n)) offers a significant performance improvement.
• Optimizing Database Queries:  A poorly written query might loop through every record in a table (O(n)), resulting in sluggish performance. Optimizing the query to use indexing (O(log n)) can drastically improve response times.

By understanding Big O Notation, we can:

• Identify potential performance bottlenecks in our code.
• Compare different algorithms and choose the most efficient one.
• Make informed decisions about data structures based on their access.

Closing thoughts

If your application needs to handle the load at scale, be mindful when the complexity is above O(log n). Because it can lead to performance degradation pretty quickly. Otherwise, always feel free to push the workload behind a queue for backend processing.

Oftentimes, experience plays a big part in our decision. We would intuitively gravitate toward our best utility. Like leveraging on well-known library/function. When it comes to performance, be mindful and throw yourself the Big O question. It just helps you to think more critically.

Big O is a guide, not a strict rule

Just remember, Big O is a guide, not a strict rule. Sometimes, a simpler algorithm with worse Big O complexity might be preferable because of its readability.

Mastering Big O Notation is an investment in your engineering toolkit. It empowers us to write efficient and scalable software, ultimately creating a better user experience. So, next time you’re faced with an algorithmic decision, think Big O!