Ordering by asymptotic growth rates

  1. Rank the following functions (refer book for the list) by order of growth; that is, find an arrangement , , , of the functions satisfying , , , . Partition your list into equivalence classes such that functions and are in the same class if and only if .
  2. Give an example of a single non-negative function such that for all functions in part (a), is neither nor .

1. Rank of The Functions Let us first try to simplify as many functions as we can:


The required order of the functions is as follows:


2. Example Function An example of a single non-negative function such that for all functions in part (a), is neither nor is:

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.