perimosocordiae/bigo

Symbolic representation of big-O notation

bigO

Symbolic representation of big-O notation.

I was looking for something like this but couldn't find it. So I wrote it, and it turned out to be much simpler than I expected.

Note that much of this functionality can now be achieved using sympy.series.order, if you're careful to specify that your limits go to infinity.

Usage

import sympy
from bigO import O, n

f_time = O(n)
g_time = O(n**2)
h_time = O(sympy.sqrt(n))

fastest_asymptotically = min(f_time, g_time, h_time)
# = h_time

total_time = f_time.inside(g_time).followed_by(h_time)
# = O(n**3)

# If you prefer a less verbose API:
total_time = f_time * g_time + h_time
# = O(n**3)

bigo's Issues

Support basic arithmetic operators

# this works
O(n).inside(O(n**2)).followed_by(O(sympy.sqrt(n))) == O(n**3)

# it would be great if this worked
O(n) * O(n**2) + O(sympy.sqrt(n)) == O(n**3)

Support for multiple variables

Right now we're restricted to comparing complexities of one variable, and that variable must be the same.