What is the order of an algorithm? Are these of same order $2^n$ and $3^n$

Question

I've two algorithms A whose complexity is $2^n$ and B whose complexity is $3^n$? I've to find the relation between their orders in big-O notation.
My attempt: As i think order is the highest degree of the polynomial. So i have to find out $2^n=n^?$ and $3^n=n^?$
Let $2^n=n^{k_1}$ and $3^n=n^{k_2}$ then $$k_1=\frac{n}{\log_2n}\implies k_1=\log_32\left(\frac{n}{\log_3n}\right)$$ Similarly $$k_2=\frac{n}{\log_3n}$$ Since $\log_32<1$ so $k_1<k_2$ and so $2^n=O(3^n)$
Am i correct or not? Please explain.

Answer 1

Recall that two complexities $f(n)$ and $g(n)$ are of the same order if $\lim_{n \to \infty}\frac{f(n)}{g(n)}$ exists and is not zero. So what you need to do is determine whether $\lim_{n \to \infty}\frac{2^n}{3^n}$ exists and is not zero.

For polynomials, you're correct that the exponent of the highest-order term determines the order; for example, $n^3 + 3n + 6$ and $n^3 + 126n^2 - n + 1$ are of the same order, but $n^4$ has higher order than either of them. But this rule is only useful for functions that can be bounded by polynomials; $2^n$ and $3^n$, being exponential, cannot.

Answer 2

Notice the following: for all $x$, $2^{n} \leq 3^{n}$. Correct? By definition, $f(n) \in O(g(n))$ if there exists a $k$ s.t. for all sufficiently large $n\geq n_{0}$, $f(n) \leq k\cdot g(n)$. Well, we can just take $n_{0}=0,k=1$ — this is what we just asserted earlier. So we have that $2^{n} \in O(3^{n})$.

EDIT: Oops, too late.