Addition Rule

Here's how to add two functions in normal form:

• $(n)^{a_0} (\log n)^{a_1} (\log \log n)^{a_2} \ldots (\log^{(k)}(n))^{a_k}$
• $+ (n)^{b_0} (\log n)^{b_1} (\log \log n)^{b_2} \ldots (\log^{(k)}(n))^{b_k}$
• $= (n)^{c_0} (\log n)^{c_1} (\log \log n)^{c_2} \ldots (\log^{(k)}(n))^{c_k}$

where c_i = a_i unless b_i > a_i and a_j = b_j for all $0\le j<i$ (in which case c_i = b_i). Also, technically, we might need to pad out either a or b so they are the same length and then drop the trailing zeros from c.

Example:

• $n \log n + \sqrt{n} (\log \log n)^2$
• a₀ = 1, a₁ = 1, a₂ = 0, b₀ = 1/2, b₁ = 0, b₂ = 2.
• Therefore, c₀ = 1, c₁ = 1, c₂ = 0.
• So, $n \log n + \sqrt{n} \log^2 n = \Theta(n\log n)$.

Idea: Whichever function has the largest power of n wins, with ties broken by the largest power of $\log n$, then $\log \log n$, and so on.

Note: Maximization is the same.