1
$\begingroup$

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)$

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.