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$
5
  • 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$ Commented Feb 3, 2014 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
    Commented Feb 3, 2014 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
    Commented Feb 4, 2014 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
    Commented Feb 4, 2014 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
    Commented Feb 4, 2014 at 17:21

1 Answer 1

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$
3
  • $\begingroup$ This says nothing that isn't already contained in my comment to the question. $\endgroup$ Commented Feb 4, 2014 at 8:00
  • 4
    $\begingroup$ @DavidRicherby So why did you not post an answer? $\endgroup$
    – Raphael
    Commented Feb 4, 2014 at 9:50
  • $\begingroup$ Why we have to use constant K=8? I am not getting it $\endgroup$ Commented Feb 11, 2014 at 0:04

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.