Legend. X Y in row M, column N: for all f, M(f) = O(N(f)X) and exists f, M(f) = O(N(f)Y).
Tip. Click a cell to view more information including how the tightest relation was obtained and references.

Any modifications below will be saved, but on your computer only. To contribute, please use the "export" button above and send the file downloaded to sxyu at
To add custom complexity measures or change the order of measures and functions, please edit the exported JSON file (which should be human-readable) directly, then import it using the file selector above. The GUI for editing measures is not ready yet.


Known asymptotic relations between measures. Click a row below to see cells using the relation in the table above. A gray row indicates the bound is tight, while red indicates the bound is superseded by another or contradicts a separation.

M1 M2 M1 = Õ(M2X) Description Attribution
Add Relation: M1 = Õ(M2X)


Asymptotic complexity measure of functions (nX). Click any cell in a complexity measure column to edit the known lower/upper bounds of that measure for the function. Click the edit icon on the rightmost column to edit description and attributions.

Edit complexity of:

Leave box blank below to indicate no upper bound or lower bound.

Add Function