1

Searching for one definition of $f : \mathbb{N} \rightarrow \mathbb{N}$

with $f' : \mathbb{N} \rightarrow \mathbb{N} $ defined with $f'(n) := f(n+1) - f(n)$

with the bounderies $f=O(f')$ and $f \not= \ \theta(f')$

Definition:

$f=O(f') \Leftrightarrow \exists n_0 \in \mathbb{N} : \forall n \geq n_0 | f(n) \leq c_1 f'(n) $ und $f\not=\theta(f') \Leftrightarrow \not \exists n_0 \in \mathbb{N} : \forall n \geq n_0 | c_2f'(n) \leq f(n) \leq c_3 f'(n) $

I think i had to show that there is no $n_0$ the boundaries, but witg the $f'$ definition its not clear for me how to do this.

Alex Ravsky
  • 90,434
Roby
  • 125
  • 3

1 Answers1

1

It seems the following.

Let $f(n)=n!$. Then $f'(n)=(n+1)!-n!=n\cdot n!$. So $f=O(f')$, but $f \not= \ \theta(f')$

Alex Ravsky
  • 90,434
  • WOW great!!Is there a way of getting this solution ? Or was i an the right track but did not think about such a solution – Roby Dec 14 '14 at 07:23
  • @Roby I had the following intuition. If $f$ grows slowly, then there is no essential difference between $f(n)$ and $f(n+1)$, so then $f’=O(f)$. So I considered a simple function $f$ which grows fast. It was $f(n)=n!$. – Alex Ravsky Dec 14 '14 at 07:34
  • Hey, im sorry.. wanted to show that there is no $c_2$ for $\theta(f')$ with this inequality $c_2 n \leq 1$ but that istn true ? :-/ – Roby Dec 15 '14 at 06:10
  • @Roby For each $c_2>0$ there exists a number $n$ such that $c_2n>1$. In fact this is axiom of Archimedes. :-) – Alex Ravsky Dec 15 '14 at 08:06
  • you are right, thanks :) – Roby Dec 15 '14 at 11:05