# Big-Oh Notation

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

For example, I want something like:

MinBigOh[...]


where

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


or

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.

Thanks!

-
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

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

Clear[BigO]
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:

Clear[MinBigO]
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 *)

-
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. –  rm -rf 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. –  rm -rf 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.

-

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]
*)
`
-