Big Theta

The notion of asymptotic growth can be used to partition the space of functions.

Two functions f(n) and g(n) are ``equal'' if neither is asymptotically bigger than the other. We write this as tex2html_wrap_inline352 .

Formally, tex2html_wrap_inline352 if and only if there exists scaling factors tex2html_wrap_inline356 and tex2html_wrap_inline358 and threshold tex2html_wrap_inline316 such that tex2html_wrap_inline362 for all tex2html_wrap_inline320 .

It's a an f(n) sandwich on g(n) bread!


next up previous
Next: Examples Up: ASYMPTOTIC GROWTH Previous: Counterexample