1
$\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$

1 Answer 1

1
$\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$
2
  • $\begingroup$ ok thank you, I'll talk to the TA about this, thank you for taking the time to answer $\endgroup$
    – zython
    Commented Apr 15, 2018 at 18:38
  • 1
    $\begingroup$ I've made an errror: the assignment said, Id have to prove or disprove the statement $\endgroup$
    – zython
    Commented Apr 16, 2018 at 14:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .