# Rank functions of n by their order of growth

I'd like to rank some functions according to their order of growth (e.g. n^2 < n^3). I'm not sure how to do order of growth in mathematica, so I was trying to rank the functions by their Limit[x,x->Infinity]. Here's what I have so far:

v = {2^(Log[2, n]), n^(1/2), Log[10, n], 2^(2^n), Log[2, Log[2, n]],
n*Log[2, n], n!, Iteratedlog[2, n], 1, n^3,
Log[2, n], (n^2)*Log[2, n], n, n^n, 100, n^2, 2^(2^(n + 1)), 2^n}

Sort[v, Limit[#1, n -> Infinity] < Limit[#2, n -> Infinity] &]


However, this doesn't even seem to work to sort the functions as a limit. What steps should I take to solve my problem?

Thanks!

• possible duplicate of Growth of functions Jan 31, 2014 at 15:21
• @Sektor Thanks! I found another related (but not duplicate) one, probably the one I was thinking of because I answered it (poorly): Big-Oh Notation Jan 31, 2014 at 15:33
• @Mr.Wizard It gives a different perspective, it is not the traditional approach one might consider - still, it is working, so :) Jan 31, 2014 at 15:35

Don't compare values that are likely to be infinities. Instead, compute Limit on ratios of arguments to be sorted:

Sort[v, Limit[#1 / #2, n -> Infinity] < 1 &]


You need to use valid functions, though; whatever Iteratedlog is, it's going to be nonsensical on this comparison as it's not defined. Mathematica silently skips complaining about it, though.

Of course, if you consider growth towards negative infinity "growth", you probably want to add Abs in the comparison function.

EDIT: Indeed treatise linked by Sektor in comments is much more rigorous. Mine just performs the comparison it directly implies: whether ratio of equations is below or above (or equal) to 1. OTOH, my code doesn't really show which functions belong to different growth classes, so you could naively say it does the job...

• Thanks for the functions suggestion. I'll fix that in the post right now. Jan 31, 2014 at 15:11
• The iterated logarithm is known by Wolfram|Alpha? Jan 31, 2014 at 17:18
• I don't think Mathematica has anything that would resemble iterated logarithm as a built-in definition, nor trivial definition like IteratedLogarithm[x_, i_] := i /; x <= 1; IteratedLogarithm[x_, i_] := IteratedLogarithm[Log[x], i + 1]; IteratedLogarithm[x_] := IteratedLogarithm[x, 0]; could really be used with Limit. Jan 31, 2014 at 18:45