complexity involving exponential of different order

18 Views Asked by At

I have an algorithm of complexity $O\left(x 3^x+6^{x/2}\right)$.

Can this then be equivalent to $O\left(6^{x/2}\right)$ or is it not further reducible?

And another related question is $O\left(x 3^x+6^{x/2}\right)$ better than $O\left(6^x\right)$?

1

There are 1 best solutions below

0
On BEST ANSWER

HINT $$ 6^{x/2} = \left(6^{1/2}\right)^x = \left(\sqrt6\right)^x \approx 2.45^x $$

So what is the real order of $3^x + 6^{x/2}$? How about the real order of $x 3^x + 6^{x/2}$?