0
$\begingroup$

I am a little confused on how to prove/disprove Big O.

For the problem, $2^{n+3}= O(2^n)$, I did the following:

$$2^{n+3} \leq K \times 2^n$$

Set $K = 1$

$$2^{n+3} \leq 2^n$$

Test for large values of n (so I plugged in n = 100)

$2^{103} \leq 2^{100}$ --- which is false therefore Big O is disproven

Is this process correct?

$\endgroup$
  • 3
    $\begingroup$ No, it's not correct. $2^{n+3}$ is $O(2^n)$ if there exists a constant $c$ such that $2^{n+3}\le c2^n$ for all large enough $n$. All you have shown is that $c\neq 1$; you need $c=8$. $\endgroup$ – David Richerby Feb 3 '14 at 23:28
  • $\begingroup$ Thanks. That makes sense. Is there a method to prove them without picking values for 'c' and 'n' or is that the only way? $\endgroup$ – user13371 Feb 3 '14 at 23:33
  • 1
    $\begingroup$ "which is false therefore Big O is disproven" -- wrong. Wrong! Landau notation says something about behaviour in the limit; you can not disprove such a relation with a finite sample! $\endgroup$ – Raphael Feb 4 '14 at 9:52
  • 1
    $\begingroup$ @Raphael, the "it fails for this single case, therefore it is false" is sadly widespread. Here it even adds a parameter $K$, arbitrarily set to 1... $\endgroup$ – vonbrand Feb 4 '14 at 16:23
  • $\begingroup$ @vonbrand Sad, but probably won't change as long as we keep telling people to just plot it without warning. $\endgroup$ – Raphael Feb 4 '14 at 17:21
1
$\begingroup$

Just, replace the constant $K = 2^3$, and you have to use this constant for your proof.

$$ 2^{n+3} = K\times 2^n$$

So, $O(2^{n+3}) = O(2^n)$.

$\endgroup$
  • $\begingroup$ This says nothing that isn't already contained in my comment to the question. $\endgroup$ – David Richerby Feb 4 '14 at 8:00
  • 4
    $\begingroup$ @DavidRicherby So why did you not post an answer? $\endgroup$ – Raphael Feb 4 '14 at 9:50
  • $\begingroup$ Why we have to use constant K=8? I am not getting it $\endgroup$ – rohan-patel Feb 11 '14 at 0:04

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.