Multiplication Rule

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

• $(n)^{a_0} (\log n)^{a_1} (\log \log n)^{a_2} \ldots (\log^{(k)}(n))^{a_k}$
• $\times (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+b_i.

Example:

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

Idea: Add the corresponding exponents.