# f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?

All functions are from naturals to naturals.

Let f(n) and g(n) be monotonically increasing functions. prove or disprove h(n) = max(f(n),g(n)) => h = O(f) or h = O(g)

I've found close questions regarding max(f,g) being O(f+g) but I couldn't derive anything from them regarding my specific problem. Needless to say, I'm new to algorithms and data structures.

any explanations, solutions would be great :)

• "max(f,g) being O(f+g)" -- start from there. How do O(f+g), O(f) and O(g) related? Try some examples first, then formulate a hypothesis! – Raphael Nov 1 '17 at 10:15
• I've come to understand that this is not true, meaning there are functions f and g such that sometimes f<g and sometimes f>g. but I can't come up with specific functions as such. – MatanyaP Nov 1 '17 at 10:50
• It is true that such functions exist (consider $x \mapsto 0.5$ and $x \mapsto \sin x$). The question is how that relates to the claim. – Raphael Nov 1 '17 at 11:46

That's not true. Let's define $f$ and $g$:

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

They look odd, but you can easily proof (by induction), that: max\{f, g\}(x) = \left\{\begin{aligned} &2^{x}g(x) && x \equiv 0 \mod 2\\ &2^{x}f(x) && 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:

1. multiply by $2$ since, another function is multiplied by $2$,
2. multiply by $2^{x-1}$, because another function was already greater by that factor,
3. 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) < cf(x)$$ nor $$max\{f, g\}(x) < cg(x)$$.

• amazing, tnx a a lot it really helped :) – MatanyaP Nov 2 '17 at 6:19