f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?
That's not true. Let's define $f$ and $g$:

$$
f(x) = \left\{\begin{aligned}
&amp;1 &amp;&amp; x = 0\\
&amp;2f(x-1) &amp;&amp; x \equiv 1 \mod 2\\
&amp;4^xf(x-1) &amp;&amp; \text{otherwise}
\end{aligned}
\right.$$
$$
g(x) = \left\{\begin{aligned}
&amp;1 &amp;&amp; x = 0\\
&amp;4^xg(x-1) &amp;&amp; x \equiv 1 \mod 2\\
&amp;2g(x-1) &amp;&amp; \text{otherwise}
\end{aligned}
\right.$$

They look odd, but you can easily proof (by induction), that:
$$
max\{f, g\}(x) = \left\{\begin{aligned}
&amp;2^{x}g(x) &amp;&amp; x \equiv 0 \mod 2\\
&amp;2^{x}f(x) &amp;&amp; x \equiv 1 \mod 2
\end{aligned}
\right.$$

Intuition behind this is that for each number $x$ we 'increase' value of one function by $2$ and one by $4^x$. Increasing first function is straight forward, just for keeping function strictly increasing. Multiplication of second function is more interesting. Since $4^x = 2 \cdot2^{x-1}\cdot2^x$, we can split this operation into 3 steps:


multiply by $2$ since, another function is multiplied by $2$,
multiply by $2^{x-1}$, because another function was already greater by that factor,
multiply by $2^{x}$, because we want our function to be greater by this factor


Now you can easily see, that there is no constant $c$ for which $$max\{f, g\}(x) &lt; cf(x)$$ nor $$max\{f, g\}(x) &lt; cg(x)$$.