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:

Direct link:

Examples

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(n^{2.529}) time.
[Zwick'02].

Sankowski's dynamic APSP algorithm with O(n^{1.897}) update time.
[Sankowski'05].

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

Dynamic single source distances in O(n^{1.816}) update time.
[BN'19].

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."
}