0

Does there exist a function $()$ such that it satisfies both $() ∈ (^3 )$ and, $() ∈ Θ(^3)$? (here $o()$ is little oh and $Θ()$ is big theta) Can some one help with a proof?

Gary
  • 31,845
anomaly_0246
  • 1
  • 1
    What have you tried? Have you tried writing down the definitions and see if they can happen at the same time? – Gary Feb 14 '22 at 23:05
  • I'm trying to find an constant c value to derive an contradiction.But i'm not too familiar with the approach of finding an appropriate C value. Do you have any idea on how to do that ? – anomaly_0246 Feb 15 '22 at 00:53
  • The little-o statement says that $f(n)/n^3$ is eventually smaller than any positive constant (since the ratio tends to $0$). The big-Theta states that this ratio is bounded from below by a fixed positive number. Can you see what is the issue? – Gary Feb 15 '22 at 01:03

1 Answers1

0

$f \in o(n^3)$ implies $\frac{f(n)}{n^3} \to 0$.

$f \in \Omega(n^3) \subseteq \Theta(n^3)$ implies there exists $C > 0$ such that $\frac{f(n)}{n^3} \ge C$ for all large $n$.

angryavian
  • 89,882
  • Are you suggesting that they are mutually exclusive ?Can you please elaborate by taking an example of arbitary constant? – anomaly_0246 Feb 17 '22 at 01:38