Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby

More Notation-Theta and Little Oh

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

A notation, , to describe a function which is both O(g(n)) and , for the same g(n). (Definition ).
A notation, , to describe a function which is O(g(n)) but not , for the same g(n). (Definition ).

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

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

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

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 implies that .

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