I have a question that states:

Let $f(n)$ and $g(n)$ be positive non-decreasing functions such that $(f(n)−g(n)) = Θ(1)$. Prove that $f(n) = Θ(g(n))$.

The question's solution is one that I do not understand:

By definition, there exists $c_1, c_2 > 0$ such that for $n > n_0$ we have $$c_1 \leq f(n) - g(n) \leq c_2$$.

This shows that for $n > n_0$ we have: $$g(n) \leq c_1 + g(n) \leq f(n)$$.

Since $g(n) > 0$ and $g(n)$ is non-decreasing, we get that for $n > n_0$ we have: $$\frac{f(n)}{g(n)} - 1 \leq \frac{c_2}{g(n)} \leq \frac{c_2}{g(1)}$$

Given this, it follows that: $$f(n) \leq (\frac{c_2}{g(1)} + 1) \cdot g(n)$$

I don't really understand the proof here, and I especially don't understand how this proves that $f(n) = \Theta(g(n))$, because if you take $f(n) = 1$ and $g(n) = \frac{1}{n}$, this will give you $f(n) \neq \Theta(g(n))$. Can anyone help me understand?

Edit: I see now that the "counterexample" I provided is not a non-decreasing function. I guess it makes sense now...

Thank you.

  • 2
    $\begingroup$ You want to show that there is a positive constant $C$ so that $\dfrac{f(n)}{g(n)} \le C$. Didn't that algebra establish that? (Ordinarily this notation is used when the functions go to $\infty$ as $n\to\infty$, but I guess this isn't quite needed here.) $\endgroup$ – Ted Shifrin Feb 13 '18 at 19:17

Your Answer

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

Browse other questions tagged or ask your own question.