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 na×nb by nb×nc matrix.

input: ~

complexity: ~

parameters: ~

Optimization method:

Direct link:


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

Zwick's APSP algorithm which runs in O(n2.529) time.

Sankowski's dynamic APSP algorithm with O(n1.897) update time.

The dynamic matrix inverse algorithm by v.d.Brand, Saranurak & Nanongkai with O(n1.406) update time.

Dynamic single source distances in O(n1.816) update time.


Author: Jan van den Brand.
The bounds on the matrix exponent omega(a,b,c) are computed using current best bounds on rectangular matrix multiplication by [Le Gall, Urrutia'18].
This implementation uses Math.js, fmin and jsLPSolver.
I thank Yin Tat Lee, Shay Golan and Adam Karczmarz for suggestions and bug reports.

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{}", note = "Tool to balance complexity terms depending on fast matrix multiplication." }