Chapter 9Complexity Analysisslides.en.pdf:206

Big-O Arithmetics

Drop constants, drop small summands, distribute

Theorem 0.6 — Computing with Landau sets

Concept

Landau notation is meant to suppress noise. Three useful arithmetical rules
let us simplify expressions without losing the growth class:

1. Drop constant factors.

c \cdot f(n) \in O(f(n)) \quad \text{for any constant } c > 0

Example:

5n^2 \in O(n^2)

2. Drop lower-order summands.

f(n) + g(n) \in O(\max(f(n), g(n)))

Example:

n^2 + 100n + 7 \in O(n^2)

3. Distribute over products.

O(f) \cdot O(g) = O(f \cdot g)

Example:

O(n) \cdot O(\log n) = O(n \log n)

Putting them together:

7n^3 + 5n^2 \log n + 1000n \in O(n^3)

Why? The highest-degree term is

7n^3

. The next is

5n^2 \log n

, which is

O(n^3)

since

\log n \leq n

for

n \geq 1

. Sum them: still

O(n^3)

Common mistakes to avoid:
- $O(f + g) = O(f) + O(g)$ is WRONG. $O$ doesn't distribute over $+$ . Use
the rule $f + g \in O(\max(f, g))$ .
- $O(n + n^2) = O(n^2)$ , not $O(2n^2)$ . Constants don't matter.
- $O(2^n) \cdot O(2^n) = O(2^n \cdot 2^n) = O(4^n)$ , still exponential.

Logarithm tricks:
- $\log(a^b) = b \log a$
- $\log(ab) = \log a + \log b$
- $\log_2 n = \frac{\log n}{\log 2} \in \Theta(\log n)$ — the base of a log
doesn't matter (just a constant factor).

Practice — score 100% to advance

Multiple choice

Simplify

5n^2 + 3n + 100

to a Landau class.

What is

O(n) \cdot O(\log n)

Why can we drop a constant factor?

O(2^n) \cdot O(2^n)

simplifies to…

7n^3 + 100 n^2 \log n \in

___?

Fill in the blank

O(f) + O(g) = O(\text{

}(f, g))

— take the ___ of the two growth rates.

O(f) \cdot O(g) = O(\text{

})

— multiply growth rates when combining sequential work.

Loading…