How to find witnesses for big O

Question

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?

Answer 1

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.