Black-Box Complexity
lIf
we see
T(n) / f(n) < c
T(n) / f(n) < c
lthen the hypothesis T(n) ë O(f(n)) is supported.
lIf T(n) / f(n) is approximately a constant as n increases, then the bound appears to be tight.
lIf T(n) / f(n) decreases as n increase, the bound is loose.
lIf T(n) / f(n) increases, we donŐt have a bound.