Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

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

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
Thanks for the functions suggestion. I'll fix that in the post right now. –  beachwood23 Jan 31 at 15:11
    
The iterated logarithm is known by Wolfram|Alpha? –  beachwood23 Jan 31 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. –  kirma Jan 31 at 18:45

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.