# Using asymptotic definitions to prove or disprove statements

The statement I am trying to prove or disprove is $$(2^n)^{1/3} \in \Theta (2n)$$. I think this is false so I attempted to disprove it. Below is my proof (disproof). I want to make sure that a) I am correct in my thought that the initial statement is false and b) My proof is a complete/well-formulated asymptotic proof. This is my first time writing my own proof like this so I am very unsure. I based the structure/strategy on the proof by account named Alt found at this link: Big O notation - Proving that a function is not O(n)

Any help is appreciated, thank you

Let $$f(n) = (2^n)^{\frac{1}{3}}$$. Suppose for contradiction that $$f(n) \in \Theta (2^n)$$. Then, by definition of Big-Theta, $$f(n) \in \Omega (2^n)$$. Then, by definition of Big-Omega, there exist positive constants $$c$$ and $$n_0$$ such that $$f(n) \geq c * 2^n$$ for all $$n \geq n_0$$. By substituting, this becomes $$(2^n)^{\frac{1}{3}} = 2^{n/3} \geq c* 2^n$$. Take the $$log_2$$ of both sides to get $$log_2(2^{n/3}) = \frac{n}{3} \geq log_2(c*2^n) = log_2(c) + log_2(2^n) = log_2(c) + n$$. Then, we are left with the inequality $$\frac{n}{3} \geq log_2(c) + n$$. Subtract $$log_2(c)$$ from both sides (and flip the inequality) to get $$n\leq \frac{n}{3} - log_2(c)$$. However, since the equality should hold for all n's and it doesn't hold for $$n=\frac{n}{3} - log_2(c) + 1$$,then there is a contradiction in the initial assumption. Therefore, $$f(n) \not\in \Theta (2^n)$$

Your work is fine. To see that $$f(n) \in \Omega(2^n)$$ is false, it suffices to note that $$\frac{f(n)}{2^n} = 2^{-2n/3} \to 0$$ as $$n \to \infty$$, which is essentially what you showed.