18
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ And have Mathematica reason about the Big-Oh running time somewhat is the hard part :D $\endgroup$
    – Dr. belisarius
    Jul 11, 2012 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, 2012 at 15:41

4 Answers 4

Reset to default
7
$\begingroup$

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 *)
Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ But what about $O(n \cdot log(n))$ etc...? $\endgroup$
    – Brett Champion
    Jul 11, 2012 at 3:34
  • $\begingroup$ @Brett Yes, that's harder... trying to think of something. $\endgroup$
    – rm -rf ♦
    Jul 11, 2012 at 4:39
  • $\begingroup$ Isn't there some simple validity to the method I propose? When does it fail? $\endgroup$
    – Mr.Wizard
    Jul 11, 2012 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, 2012 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, 2012 at 13:23
5
$\begingroup$

Since 11.3 a range of Asymptotic based functions are available.

See: https://blog.wolfram.com/2018/07/26/big-o-and-friends-tales-of-the-big-the-small-and-every-scale-in-between/

Your 

MinBigOh[2x+3, x^2]

could be implemented as 

AsymptoticLessEqual[2 x + 3, x^2, x -> Infinity]
Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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]
*)
Improve this answer
$\endgroup$

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.