# Techniques for asymptotic growth comparison between complicated expressions

For the following functions: $$\frac{2^n}{n + n \log n}$$ and $$4^{\sqrt{n}}$$

I'd like to compare their asymptotic growth as $n \to \infty$. Is there any other way to do that other than using limits? Sort of an intuitive way? Since these are not "standard" asymptotic functions, and the first function actually contains multiple functions divided , would that mean that limits are the only way to solve it to find the answer?

-

## migrated from programmers.stackexchange.comFeb 11 '13 at 13:05

This question came from our site for professional programmers interested in conceptual questions about software development.

Migrated to math.SE from programmers.SE. cs.SE rejected it since it's not explicitly about the complexity of a particular algorithm. – Thomas Owens Feb 11 '13 at 13:08
@ThomasOwens More precisely: this isn't Computer Science material because there's no apparent application to CS. It doesn't have to be the complexity of a particular algorithm, things like exercices about the master theorem are ok on Computer Science, but this question has no connection with algorithms or with common complexity functions at all. – Gilles Feb 11 '13 at 13:11

Using a bit of algebraic manipulation I get: $$4^{\sqrt{n}} = (2^2)^{\sqrt{n}} = 2^{2 \sqrt{n}}$$
I think this makes it much easier to compare the functions. Intuitively the numerator in the first function overpowers the denominator (exponential vs subexponential), so we can think of it as just $2^n$ (for sufficiently large $n$, as in the Big O sense). $2 \sqrt{n}$ is much less than n for large n thus we conclude the first function grows faster than the second.
Normally when comparing functions asymptotically, the sufficiently large n could actually be quite large. In this case though, it is low. If you plug your equations and $2^n$ into Wolfram Alpha:
the plot shows $n \approx 10$ is the sufficiently large n. Notice in the plot how $2^n$ and your first function are almost the same with your's just slightly to the right. In fact, if you plotted the graph from $1$ to $20$, the second equation barely shows up.