Sign up ×

Is there a way to have Mathematica understand Big-Oh notation?

For example, I want something like:



MinBigOh[2x+3, x^2] = 2x+3


MinBigOh[2x+3, x^2] = x

The idea here is that I want to be able to augment "Min" to understand Big-Oh comparisons.

The purpose of this is so that I can write a bunch of expressions, and have Mathematica reason about the Big-Oh running time somewhat.


share|improve this question
And have Mathematica reason about the Big-Oh running time somewhat is the hard part :D –  belisarius Jul 11 '12 at 2:56
If everything is polynomial you might get away with minBigOh[p1_, plist_List] := PolynomialReduce[p1, plist][[2]] (which is in keeping with the "term-rewritica" moniker). –  Daniel Lichtblau Jul 11 '12 at 15:41

3 Answers 3

up vote 4 down vote accepted

I would suggest something like the following, which uses the built-in O[x]^n notation to denote a term of order $x^n$.

BigO[expr_List, var_Symbol, func_] := 
     O[var]^func[Exponent[# - Coefficient[#, var, 0], var, func] & /@ expr]

Some examples:

BigO[{2 x + 3, x^2 + x^3}, x, Max]
(* O[x]^3 *)

BigO[{2 x + 3, x^2 + x^3}, x, Min]
(* O[x]^1 *)

If you only want to find the smallest order in the list of expressions, you can also use the fact that O automatically does O[x]^n + O[x]^m == O[x]^n when n ≤ m to write something like:

MinBigO[expr_List, var_Symbol] := 
    Plus @@ Thread[O[var]^Exponent[# - Coefficient[#, var, 0], var, Min] & /@ expr]

Another example:

MinBigO[{2 x + 3, x^2 + x^3}, x]
(* O[x]^1 *)
share|improve this answer
But what about $O(n \cdot log(n))$ etc...? –  Brett Champion Jul 11 '12 at 3:34
@Brett Yes, that's harder... trying to think of something. –  R. M. Jul 11 '12 at 4:39
Isn't there some simple validity to the method I propose? When does it fail? –  Mr.Wizard Jul 11 '12 at 12:06
@mr.wizard not near mma now, but I would say something like MinBigOh[10 x, 1/10^6 x^2] would fail for the specific answer. Of course, then you pick a bigger value to substitue, but you can always twiddle the coefficients to find a counter example and eventually you hit max/min machine number at which point you can no longer substitute. The objective is not whether which has a higher tunning time, but what the time complexity is. –  R. M. Jul 11 '12 at 13:12
I've never seen O notation in that form/degree before. Some reading is in order I guess. –  Mr.Wizard Jul 11 '12 at 13:23

Perhaps it is sufficient to substitute a suitably large value for x and take the smallest?

MinBigOh[expr__] := SortBy[{expr}, # /. x -> 1`*^6 &][[1]]

MinBigOh[2 x + 3, x^2]
3 + 2 x

If you do this it would be prudent to use Formal Symbols e.g. Esc$xEsc.

share|improve this answer

What about this:

MinBigOh[var_, expr1_, expr2_]:=
  If[Limit[expr1/expr2, var->Infinity]==0, expr1, expr2]

Then you get

MinBigOh[x, 2x+3, x^2]
==> 3 + 2 x
MinBigOh[x, x, Log[x]]
==> Log[x]
share|improve this answer

Your Answer

