0

I have two functions

$$g_1(n) = 1$$

$$g_2(n) = 10^{10^n}$$

I have to find one function that is neither $O(g_i(n))$ nor $Ω(g_i(n))$ ($i=1,2$). I already have : $$f(n) = 2 \sin (n)$$ That should be enough for $g_1(n)$, but I don't know how to come up with a function (or modify $f(n)$) so that it handles $g_2(n)$. I think that I should find a function that alternates near the $y$-axis.

Is there an easier way to do this?

Crostul
  • 36,738
  • 4
  • 36
  • 72
ninesalt
  • 189

1 Answers1

1

Check that $$f(n)= 10^{(-11)^n}$$ works, and it has the advantage of being always positive.

EXPLANATION: In general, for positive functions $f,g$, $f(n) \in O(g(n))$ is equivalent on saying that $$f(n) \le C g(n)$$ i.e. $f(n)/g(n)$ is bounded. Similarly, $f(n) \in \Omega(g(n))$ means that $g(n)/f(n)$ is bounded.

  1. $f (n) \in O(1)$ means that $f(n)$ is bounded

  2. $f (n) \in O(10^{10^n})$ means that $f(n)/10^{10^n}$ is bounded

  3. $f (n) \in \Omega(1)$ means that $1/f(n)$ is bounded

  4. $f (n) \in \Omega(10^{10^n})$ means that $10^{10^n}/f(n)$ is bounded

Now, note that 1 implies 2 , and 4 implies 3. So, you want to find a function $f$ not satisfying 2 and 3.

Take a function such that even indices do not satisfy 2 and odd indices do not satisfy 3, and you are done.

Crostul
  • 36,738
  • 4
  • 36
  • 72
  • Why does 1 imply 2 and 4 imply 3? – ninesalt Oct 07 '16 at 18:44
  • Also, how can point 3 be violated? If you take the limit as $n$ goes to infinity of $1/10^{-11^n}$ you get 0 – ninesalt Oct 07 '16 at 19:57
  • It's not $10^{-11^n}$. It's $10^{(-11)^n}$, which is different. For even indices this is a very large number, while for odd indices it's a small number very close to $0$. – Crostul Oct 07 '16 at 22:34