-1
$\begingroup$

how would I prove

$ 8^n = Θ(4^n)$ is either true or false.

I so far have attempted to prove big O but cant find the value of C1

$\endgroup$
14
  • $\begingroup$ This seems like a homework question. What values of $c_1$ have you tried? Remember it can also be less than 1 (but has to be greater than 0). $\endgroup$
    – ryan
    Commented Mar 24, 2019 at 23:58
  • $\begingroup$ I did it using this method link and came to $3^n<=C1$ $\endgroup$ Commented Mar 25, 2019 at 0:01
  • $\begingroup$ Oh wait, I misread. A good approach to this (when they are both exponential) is trying to convert them to a common base. For instance we can convert them both to base 2, meaning $4^n = 2^{2n}$ and $8^n = 2^{3n}$. Can you now prove if $2^{3n} = \Theta(2^{2n})$? $\endgroup$
    – ryan
    Commented Mar 25, 2019 at 0:14
  • $\begingroup$ would I do this the same way ? and sorry I meant I has 2^n <= C1 $\endgroup$ Commented Mar 25, 2019 at 0:16
  • $\begingroup$ You could draw a similar conclusion. If you know $c_1 \geq 2^n$ this would imply that $c_1$ must be greater than a non-constant value (because $2^n$ is a function of $n$). Therefore we have a contradiction that $c_1$ is not a constant, and thus no constant $c_1$ would exist for this inequality. Does this logic make sense? $\endgroup$
    – ryan
    Commented Mar 25, 2019 at 0:17

1 Answer 1

1
$\begingroup$

Just compute $\lim_{n\to\infty} \frac{8^n}{4^n} = \infty$. Hence, $8^n = \Omega(4^n)$ and also $8^n = \omega(4^n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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