I'm new to introduction to algorithms and asymptotic analysis.
I'm trying to prove/disprove this:
Let $f,g\colon\mathbb{N} \to \mathbb{N}$ be increasing functions, i.e. such that $(f(n+1)>f(n)$ and $g(n+1)>g(n))$ for all $n$.
Define $h\colon\mathbb{N} \to \mathbb{N}$ as follows: $h(n)=\max(f(n),g(n))$ for each $n \in N$.
Does it necessarily follows that $h=O(f)$ or $h=O(g)$?
Intuitively, it looks true for me but I have no idea how to prove it.
Not necessarily.
For simplicity, I'll replace the strict monotonicity recquirement by $f,g$ non-decreasing. (It does not change anything, you can always add a very small slope to make them increasing.)
Let $f$ be defined by $$f(n) = 2^{(\lfloor \log_2 n\rvert)^2}$$ i.e. $f$ is constant on each $[2^k, 2^{k+1})$ with value $2^{k^2}$.
Now, let $g$ be defined as the piecewise constant function, constant on each $[2^{3k}, 2^{3(k+1)})$ with value $2^{(3k+1)^2}$.
We have
Moreover, the ratio $\frac{f(n)}{g(n)}$ is then either $2^{(3k)^2-(3k+1)^2}= 2^{-(6k+1)}$, $1$, or $2^{(3k+2)^2-(3k+1)^2}= 2^{3(2k+1)}$. When $k\to\infty$, this shows that $\frac{f}{\max(f,g)}$ and $\frac{g}{\max(f,g)}$ both get arbitrarily close to $0$ and $\infty$.
