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) < clWe can simply examine this ratio.