How to disprove the following using negation?

Question

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$

Disprove $\forall f,g\in\mathcal{F}:$$\log{f(n)} \in O(g(n)) \implies f(n) \in O(3^{g(n)}).$

(Here we assume log has base 2)

(We disprove)

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$

Negation: $\exists f,g\in\mathcal{F}:$$\log{f(n)} \in O(g(n)) \land f(n) \not\in O(3^{g(n)}).$

Or equivalently: $[\exists c\in \Bbb{R^+}: \exists B\in\Bbb{N}:\forall n\in \Bbb{N}: n\ge B\implies \log_2{f(n)} \le cg(n)] \land [\forall c\in \Bbb{R^+}: \forall B\in\Bbb{N}:\exists n\in \Bbb{N}: n\ge B\land f(n) > c3^{g(n)}]$

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$

Let $f(n)=5^n$ and $g(n)=n$

Let $c_0=5$, then $c_0\in \Bbb{R+}$

Let $B_0=100$, then $B_0\in \Bbb{N}$

Then $\log_2{5^n}=n\log_2{5} \le {5n}$

Then $[\exists c_0\in \Bbb{R^+}: \exists B_0\in\Bbb{N}:\forall n\in \Bbb{N}: n\ge B_0\implies \log_2{f(n)} \le c_0g(n)]$

Let $c\in \Bbb{R^+}$

Let $B\in \Bbb{N}$

Let $n_0=\max{\{\log{\frac{5}{3}c},\ B\}}+1$

Then $n_0\in\Bbb{N}$

Then $n_0 > B$

Then $n_0 > \log{\frac{5}{3}c}$

Then $f(n)=5^n\ge c 3^n=c3^{g(n)}$

Then $[\forall c\in \Bbb{R^+}: \forall B\in\Bbb{N}:\exists n\in \Bbb{N}: n\ge B\land f(n) > c3^{g(n)}]$

Then $[\exists c\in \Bbb{R^+}: \exists B\in\Bbb{N}:\forall n\in \Bbb{N}: n\ge B\implies \log_2{f(n)} \le cg(n)] \land [\forall c\in \Bbb{R^+}: \forall B\in\Bbb{N}:\exists n\in \Bbb{N}: n\ge B\land f(n) > c3^{g(n)}]$

Therefore $\exists f,g\in\mathcal{F}:$$\log{f(n)} \in O(g(n)) \land f(n) \not\in O(3^{g(n)}).$

I felt my later logic is a bit messed. Could someone tell me how?

Answer 1

In general

$$\neg\left(\forall A\in U\,,\,A\implies B\right)=\exists A\in U\,A\rlap{\;\;\;\,/}\implies B\;,\;\text{or}\;\;\exists A\in U\;,\;A\,\wedge\neg B $$

In your case:

$$\exists f,\,g\in \mathcal F\;,\;\;\log f(n)=\mathcal O(g(n))\;\;\wedge\;\;f(n)\notin\mathcal O(3^{g(n)})$$