# How to prove big theta inequality?

Suppose we have functions $f,n : \mathbb{N} \rightarrow \mathbb{R}_{> 0}$.

Show that for values $n_0,c \in \mathbb{N} \ \ \forall n \geq n_0$ the following is true

$$| f(n) - g(n) | \leq cn \implies f \in \Theta(g)$$

I have seen a couple of definitions of $\Theta(f)$ this is the one I'm allowed to use:

$g \in \Theta(f) \iff g \in \mathcal{O}(f) \land f \in \mathcal{O}(g)$, and I dont think I'm allowed to use the definition with the two constants ( of $\Theta$ that is)

I have tried the following but couldnt get farther. I think I made some steps in the right direction but I'm not seeing anything.

$$wlog \ \ f(n) > g(n)$$ $$f(n) + cn \leq g(n)$$

$$f(n) -g(n) \leq \delta := c_1 f(n) - c_2g(n) \quad c = max(c_1,c_2)$$

$$\delta \leq c(f(n) - g(n) )$$

$f(n) - g(n)$ could be potentially "cut" down with modular arithmetic to fit the rest in to less than $n$ and putting the rest into our $c$.

I have tried playing around with these little snippets but as I said couldn't get farther.

# Disclaimer:

This is an assignment question, please do not post full answers, once I get the graded solution I'll post it here. I believe I have done my fair share of thinking in the task and I've shown what I know and what I dont know. I believe I deserve a hint at this point.

## 1 Answer

The claim in the problem is false. For example, $f(n) = \log n$ and $g(n) = \sqrt n$ satisfy $| f(n) - g(n) | \leq cn$ but not $f \in \Theta(g)$.

• ok thank you, I'll talk to the TA about this, thank you for taking the time to answer – zython Apr 15 '18 at 18:38
• I've made an errror: the assignment said, Id have to prove or disprove the statement – zython Apr 16 '18 at 14:04