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.


  • 1
    $\begingroup$ And have Mathematica reason about the Big-Oh running time somewhat is the hard part :D $\endgroup$ – Dr. belisarius Jul 11 '12 at 2:56
  • $\begingroup$ 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). $\endgroup$ – Daniel Lichtblau Jul 11 '12 at 15:41

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 *)
  • 3
    $\begingroup$ But what about $O(n \cdot log(n))$ etc...? $\endgroup$ – Brett Champion Jul 11 '12 at 3:34
  • $\begingroup$ @Brett Yes, that's harder... trying to think of something. $\endgroup$ – rm -rf Jul 11 '12 at 4:39
  • $\begingroup$ Isn't there some simple validity to the method I propose? When does it fail? $\endgroup$ – Mr.Wizard Jul 11 '12 at 12:06
  • $\begingroup$ @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. $\endgroup$ – rm -rf Jul 11 '12 at 13:12
  • $\begingroup$ I've never seen O notation in that form/degree before. Some reading is in order I guess. $\endgroup$ – 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.


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]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy