0

Definitions:

$\mathbb{R}^{++}=\left\{ x\mid0<x\in\mathbb{R}\right\} $

$f\left(n\right)=O\left(g\left(n\right)\right)\Leftrightarrow f\left(n\right)\in\left\{ h:\mathbb{N}\rightarrow\mathbb{R}^{+}\mid\text{s.t }\exists N\in\mathbb{N},\,\,\exists c>0\,\,s.t\,\,\forall n\geq N\,\,h\left(n\right)\leq c\cdot g\left(n\right)\right\} $

$f\left(n\right)=\Theta\left(g\left(n\right)\right)\Leftrightarrow f\left(n\right)=O\left(g\left(n\right)\right)\wedge f\left(n\right)=\Omega\left(g\left(n\right)\right)$

$f\left(n\right)=o\left(g\left(n\right)\right)\Leftrightarrow f\left(n\right)\in\left\{ f:\mathbb{N}\rightarrow\mathbb{R}^{+}\mid\text{s.t }\lim_{n\rightarrow\infty}\frac{f\left(n\right)}{g\left(n\right)}=0\right\} $

Question:

Let $f,g:\mathbb N\rightarrow\mathbb R^{++} $

Prove or Disprove:

If $f\left(n\right)=O\left(g\left(n\right)\right)$ and $f\left(n\right)\neq o\left(g\left(n\right)\right)$ then $f\left(n\right)=\Theta\left(g\left(n\right)\right)$

Not quite sure how to solve this one

CStudent
  • 67
  • I think it's worth thinking about an example, where there are subsequences of $\frac fg$ both descending and not descending to zero. – zkutch Mar 21 '23 at 18:55

1 Answers1

1

Let's take example suggested in comment: $g(n)=n^2$ and

$$f(n)=\begin{cases}n, & n = 2k \\ n^2, & n=2k+1\end{cases}$$ for $k=0,1,\cdots$

zkutch
  • 13,410