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 berkeley.edu.
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.
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.
Relations
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 |
|---|
Separations
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.