Black-Box Complexity
lSuppose
we are trying to bolster a hypothesis
T(n) ë O(f(n))
T(n) ë O(f(n))
lFrom
the definition, we know this means there is a constant c such that
for all n, T(n) < c f(n)
for all n, T(n) < c f(n)
lIf
our hypothesis is correct, we therefore expect for all n,
T(n) / f(n) < c
T(n) / f(n) < c
lWe
can simply examine this ratio.