Define function F which is big O but not big theta

419 Views Asked by At

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.

1

There are 1 best solutions below

5
On BEST ANSWER

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