Is there a library for programmatic manipulation of Big-O complexities?

Question

I'm interested in programming languages that can reason about their own time complexity. To this end, it would be quite useful to have some way of representing time complexity programmatically, which would allow me to do things like:

f_time = O(n)
g_time = O(n^2)
h_time = O(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)

I'm using Python at the moment, but I'm not particularly tied to a language. I've experimented with sympy, but I haven't been able to find what I need out of the box there.

Is there a library that provides this capability? If not, is there a simple way to do the above with a symbolic math library?

EDIT: I wrote a simple library following @Patrick87's advice and it seems to work. I'm still interested if there are other solutions for this problem, though.

Answer 1

SymPy currently only supports the expansion at 0 (you can simulate other finite points by performing a shift). It doesn't support the expansion at infinity, which is what is used in algorithmic analysis.

But it would be a good base package for it, and if you implement it, we would gladly accept a patch (nb: I am a SymPy core developer).

Be aware that in general the problem is tricky, especially if you have two variables, or even symbolic constants. It's also tricky if you want to support oscilitory functions. EDIT: If you are interested in oscillating functions, this SymPy mailing list discussion gives some interesting papers.

EDIT 2: And I would recommend against trying to build this yourself from scratch, without the use of a computer algebra system. You will end up having to write your own computer algebra system, which is a lot of work, and even more work if you want to do it right and not have it be slow. There are already tons of systems already existing, including many that can act as libraries for code to be built on top of them (such as SymPy).

Answer 2

If you're only working with big-O notation and are interested in whether one function grows more or less quickly than another, asymptotically speaking...

1. Given functions f and g
2. Compute the limit as n goes to infinity of f(n)/g(n) using a computer algebra package
3. If the limit diverges to +infinity, then f > g - in the sense that g = O(f), but f != O(g).
4. If the limit diverges to 0, then g < f.
5. If the limit converges to a finite number, then f = g (in the sense that f = O(g) and g = O(f))
6. If the limit is undefined... beats me!

Answer 3

Actually you are building/finding a Expression Simplifier which can deal with:

• + (in your terms: followed_by)
• ***** (in your terms: inside)
• ^, log, ! (to represent the complexity)
• variable (like n,m)
• constant number (like that in 2^n)

For example, as you given f_time.inside(g_time).followed_by(h_time), It could be an expression like:

n*(n^2)+(n^(1/2))

, and you are expecting an processer to make it output as:n^3.

So in general speaking, you might want to use a common expression simplifier (if you want it to be interesting, go to check how Mathemetica does it) to get a simplified expression like n^3+n^(1/2), and then you need an additional processor to choose the term with highest complexity from the expression and get rid of the other terms. That would be easy, just use a table to define the complexity order of each kind of symbol.

Please note that in this case, the expressions are just symbol, you should write it as something like string (For your example: f_time = "O(n)"), not as functions.