Analyzing Algorithms Using Big-O Notation

Introduction

Big-O notation provides a way to describe how an algorithm’s running time grows with input size. While understanding the definition is important, the real value of Big-O comes from applying it to analyze functions and code.

In practice, algorithms are rarely described by simple expressions. Instead, we often encounter combinations of loops, conditions, and multiple operations. To evaluate their efficiency, we need a systematic approach to simplify expressions and determine how the total work grows as the input size increases.

This lesson focuses on building that practical understanding. The goal is to learn how to derive Big-O complexity from mathematical expressions and from actual code.

Simplifying complex expressions

One of the key uses of Big-O notation is simplifying expressions so they are easier to analyze and compare. Instead of working with exact formulas, we focus on how the function behaves as the input size becomes large.

This involves applying a few standard rules:

• Ignore constant factors:

  • $5n$ becomes $O(n)$

• Focus on the dominant term (ignore lower-order terms):

  • $n^2+n \rightarrow O(n^2)$

  • $n^3+n^2+n \rightarrow O(n^2)$ ...