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