0
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ "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! $\endgroup$ – Raphael Nov 1 '17 at 10:15
  • $\begingroup$ 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. $\endgroup$ – MatanyaP Nov 1 '17 at 10:50
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 1 '17 at 11:46
0
$\begingroup$

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)$$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.