I'm having trouble determining the correct way (if there is one) to find the witnesses in any given big O problem.

The example I'm struggling with: $2^x + 17$ is $O(3^x)$.

I am expected to find two witnesses such that $2^x + 17 \leq C(3^x)$ whenever $x > k$.

Unfortunately, my textbook isn't very clear on how to actually find them and rather suggests to more or less guess until you get both constants to work. It is to my understanding that if one pair exists, infinitely many do.

How do you find these?

  • $\begingroup$ The witnesses are $(k,C)$, and it should read $C \cdot 3^x$. $\endgroup$
    – Raphael
    Mar 5 '15 at 19:10

In your case finding the witness is easy. We know that for all $x \geq 0$, $2^x \leq 3^x$. Also, for $x \geq 3$, $17 \leq 3^x$. So for $x \geq 3$, $2^x+17 \leq 2\cdot 3^x$.

There is no particular method at work here – just problem solving.


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.