Complexity Term Balancer

This is a little tool I created to balance complexity terms of algorithms and data structures. It's especially useful when you want to figure out the complexity of algorithms that depend on fast matrix multiplication.

Simply write one exponent per line in the text box below and the tool will balance the occuring terms to minimize the complexity.
You can use omega(a,b,c) for the exponent of rectangular matrix multiplication of an n^a×n^b by n^b×n^c matrix.

input: ~

complexity: ~

parameters: ~

Optimization method: Algebraic Numeric

Examples

This tool can be used to quickly lookup bounds on ω for certain inputs, e.g. ω(1,1,2) < 3.250385. Use Example

Zwick's APSP algorithm which runs in O(n^2.528) time.
[Zwick'02]. Use Example

Sankowski's dynamic APSP algorithm with O(n^1.896) update time.
[Sankowski'05]. Use Example

The dynamic matrix inverse algorithm by v.d.Brand, Saranurak & Nanongkai with O(n^1.405) update time.
[BNS'19]. Use Example

Dynamic single source distances in O(n^1.815) update time.
[BN'19]. Use Example

Credits

If this tool was useful in your research, teaching etc., I'd be thankful for a reference or citation.
@misc{Complexity, author = "Brand, Jan van den", title = "Complexity Term Balancer", howpublished = "\url{www.ocf.berkeley.edu/~vdbrand/complexity/}", note = "Tool to balance complexity terms depending on fast matrix multiplication." }