Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
@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
add comment

migrated from programmers.stackexchange.com Feb 11 '13 at 13:05

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

1 Answer

up vote 4 down vote accepted

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:

plot 2^(2sqrt(n)),  (2^n)/(n + log2(n)), 2^n  from 1 to 14

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.