Data Structures and Algorithms with Object-Oriented Design Patterns in C#
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_inline58277. We say that ``f(n) is theta g(n),'' which we write tex2html_wrap_inline59345, if and only if f(n) is O(g(n)) and f(n) is tex2html_wrap_inline59323.

Recall that we showed in Section gif that a polynomial in n, say tex2html_wrap_inline58775, is tex2html_wrap_inline58597. We also showed in Section gif that a such a polynomial is tex2html_wrap_inline59361. Therefore, according to Definition gif, we will write tex2html_wrap_inline59363.

Definition (Little Oh)     Consider a function f(n) which is non-negative for all integers tex2html_wrap_inline58277. 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_inline59331.

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_inline59395 implies that tex2html_wrap_inline59397.gif

For example, consider the function f(n)=n+1. Clearly, tex2html_wrap_inline58309. Clearly too, tex2html_wrap_inline59403, since not matter what c we choose, for large enough n, tex2html_wrap_inline59409. Thus, we may write tex2html_wrap_inline59411.


next up previous contents index

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