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?


  • 1
    $\begingroup$ possible duplicate of Growth of functions $\endgroup$
    – Sektor
    Jan 31, 2014 at 15:21
  • $\begingroup$ @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 $\endgroup$
    – Mr.Wizard
    Jan 31, 2014 at 15:33
  • $\begingroup$ @Mr.Wizard It gives a different perspective, it is not the traditional approach one might consider - still, it is working, so :) $\endgroup$
    – Sektor
    Jan 31, 2014 at 15:35

1 Answer 1


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...

  • $\begingroup$ Thanks for the functions suggestion. I'll fix that in the post right now. $\endgroup$ Jan 31, 2014 at 15:11
  • $\begingroup$ The iterated logarithm is known by Wolfram|Alpha? $\endgroup$ Jan 31, 2014 at 17:18
  • $\begingroup$ 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. $\endgroup$
    – kirma
    Jan 31, 2014 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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