Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

More Notation-Theta and Little Oh

This section presents two less commonly used forms of asymptotic notation. They are:

Definition (Theta)     Consider a function f(n) which is non-negative for all integers tex2html_wrap_inline57996. We say that ``f(n) is theta g(n),'' which we write tex2html_wrap_inline59064, if and only if f(n) is O(g(n)) and f(n) is tex2html_wrap_inline59042.

Recall that we showed in Section gif that a polynomial in n, say tex2html_wrap_inline58494, is tex2html_wrap_inline58316. We also showed in Section gif that a such a polynomial is tex2html_wrap_inline59080. Therefore, according to Definition gif, we will write tex2html_wrap_inline59082.

Definition (Little Oh)     Consider a function f(n) which is non-negative for all integers tex2html_wrap_inline57996. We say that ``f(n) is little oh g(n),'' which we write f(n)=o(g(n)), if and only if f(n) is O(g(n)) but f(n) is not tex2html_wrap_inline59050.

Little oh notation represents a kind of loose asymptotic bound  in the sense that if we are given that f(n)=o(g(n)), then we know that g(n) is an asymptotic upper bound since f(n)=O(g(n)), but g(n) is not an asymptotic lower bound since f(n)=O(g(n)) and tex2html_wrap_inline59114 implies that tex2html_wrap_inline59116.gif

For example, consider the function f(n)=n+1. Clearly, tex2html_wrap_inline58028. Clearly too, tex2html_wrap_inline59122, since not matter what c we choose, for large enough n, tex2html_wrap_inline59128. Thus, we may write tex2html_wrap_inline59130.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.