3
$\begingroup$

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh.

I can't quite figure this out, can someone help explain why this is true?

3 Answers 3

1

We have $f(n)\leq \max\{f(n),g(n)\}$ and $g(n)\leq \max\{f(n),g(n)\}$. As $f(\cdot)$ and $g(\cdot)$ are non-negative, we get $f(n)\cdot g(n)\leq \max\{f(n),g(n)\}^2,$ what is wanted (take the constant equal to $1$ in the definition).

1

Another way, though with a worse constant:

Once $f$ and $g$ are positive, $f g =(f+g)^2-f^2-g^2 $, so

$\begin{align} |fg| &\le (f+g)^2+f^2+g^2\\ &\le (2\max(f, g))^2+2(\max(f,g))^2\\ &= 6(\max(f, g))^2\\ &= O(\max(f, g))^2\\ \end{align} $

1

Here is a proof that minimizes the number of 'surprises', i.e., one which I designed by just following the shape of the formulae.

Directly using the definition, I would calculate \begin{align} & f(n) \times g(n) = O((f(n) \text{ max } g(n))^2) \\ \equiv & \qquad \text{"definition of $\;O\;$"} \\ & \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: k \times f(n) \times g(n) \le (f(n) \text{ max } g(n))^2 \rangle \rangle \\ \equiv & \qquad \text{"square of max = max of squares, since $\;f(n) \ge 0\;$ and $\;g(n) \ge 0\;$, for l.e. $\;n\;$"} \\ & \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: k \times f(n) \times g(n) \le f(n)^2 \text{ max } g(n)^2 \rangle \rangle \\ \equiv & \qquad \text{"basic property of $\;\text{max}\;$"} \\ & \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: k \times f(n) \times g(n) \le f(n)^2 \;\lor\; k \times f(n) \times g(n) \le g(n)^2 \rangle \rangle \\ \equiv & \qquad \text{"divide by $\;f(n)\;$, which is $\;\ge0\;$ for l.e. $\;n\;$; same for $\;g(n)\;$"} \\ & \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: f(n) = 0 \;\lor\; k \times g(n) \le f(n) \\ & \phantom{\langle \exists k : k > 0 : \langle \forall_{l.e.} n ::} \lor\; g(n) = 0 \;\lor\; k \times f(n) \le g(n) \rangle \rangle \\ \Leftarrow & \qquad \text{"choose $\;k := 1\;$ -- this seems the simplest most symmetrical choice"} \\ & \langle \forall_{l.e.} n :: f(n) = 0 \;\lor\; g(n) \le f(n) \;\lor\; g(n) = 0 \;\lor\; f(n) \le g(n) \rangle \\ \equiv & \qquad \text{"real numbers are a total order, i.e., $\;x \le y \;\lor\; y \le x\;$"} \\ & \text{true} \end{align} Note that this proof only assumes that $\;f,g\;$ are eventually non-negative: we did not need to assume that they are increasing.