Big-O Notation, pronounced as "Big Oh," is a standard way to describe how the running time or memory usage of an algorithm scales with the size of the input, n. It focuses on the upper bound of growth, which helps us understand the worst-case scenario of how an algorithm performs as the input gets larger.

• Purpose: It measures the efficiency of algorithms by providing a way to compare their performance for large inputs.
• Common Use: In real-world scenarios, it’s often used to determine whether an algorithm is suitable for solving a problem within acceptable time limits.

How is Big-O Notation Written?

Big-O is written in the form O(g(n)), where:

• g(n) is a function representing the growth rate of the algorithm.
• The expression O(g(n)) means that for large enough n, the function being analyzed (let’s call it f(n) does not grow faster than a constant multiple of g(n).

Breaking Down Big-O: Formal Definition

The formal definition of Big-O notation states that a function f(n) is O(g(n)) if there exists a constant C and a threshold value n₀ such that:

f(n) \leq C \cdot g(n)

for all n \geq n₀.

• C is a positive constant that scales the function g(n) so that f(n) does not grow faster than a constant multiple of g(n).
• n₀ is the point beyond which the inequality holds for all n.

Why Do We Use Big-O?

Big-O notation helps simplify complex expressions by focusing on the dominant term and ignoring less significant terms and constants. This is because, for large inputs, the term with the highest growth rate will have the biggest impact on performance.

Example: Determining Big-O for f(n) = n(n - 1)/2

Let’s see how we can find the Big-O notation for a specific function:

1. Given Function:

f(n) = \frac{n(n - 1)}{2}

2. Expand the Function:

   Simplify the expression:

f(n) = \frac{n^2 - n}{2}

3. Choosing a Suitable Upper Bound (g(n)):

   We aim to find a function g(n) such that:

\frac{n^2 - n}{2} \leq C \cdot g(n)

Let’s try g(n) = n^2. Now we need to check if we can find a constant C so that:

\frac{n^2 - n}{2} \leq C \cdot n^2

4. Simplify the Inequality:

   Divide both sides by n^2:

\frac{1 - \frac{1}{n}}{2} \leq C

5. Find a Suitable Constant (C):

   As (n) grows, the term \frac{1}{n} becomes very small, making 1 - \frac{1}{n} close to 1. Therefore, we can choose:

C = \frac{1}{2}

This choice satisfies the inequality for all n \geq 1.

6. Conclusion:

   Since we found a constant (C) and a threshold (n₀ = 1), we conclude that:

f(n) = O(n^2)

This example demonstrates how to determine Big-O notation by finding an upper bound function and proving that the original function is bounded by that function, within a constant factor.

Why Do We Ignore Lower-Order Terms and Constants?

In Big-O analysis, we focus on the dominant term because it has the most significant impact on the growth rate as (n) becomes large.

• Lower-order terms: As the input size grows, terms like n in n^2 - n become less significant compared to n^2.
• Constant factors: Multiplicative constants like 2 in 2n^2 don't affect the growth rate classification since Big-O measures relative growth.

Common Big-O Notations and Their Meanings

Here are some commonly used Big-O notations and what they represent:

These examples show how different functions behave and how Big-O notation helps categorize the growth patterns.

Key Points to Remember

1. Big-O Represents an Upper Bound: It describes the maximum growth rate of an algorithm.
2. Focus on the Dominant Term: For large inputs, the term with the highest growth rate matters most.
3. Ignore Constants and Lower-Order Terms: These do not significantly affect growth for large input sizes.