0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

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.