Chapter 4, Problem 13R

Explanation of Solution

Ordering the asymptotic growth rate:

Given functions are ordered as follows:

${\text{2}}^{\text{10}}{\text{,2}}^{\text{logn}}{\text{, 3n+100logn, 4n, nlogn, 4n logn+2n, n}}^{\text{2}}{\text{+10n, n}}^{\text{3}}{\text{, and 2}}^{\text{n}}$

Explanation:

The above function s ordered from least to greatest based on the asymptotic functions.

• $2^{10}$ is the constant time and so it is ordered first.
• ${\text{2}}^{\text{logn}}$ is linear $\text{O}\left(\text{n}\right)$ according to the definition of log.
• $\text{3n+100logn}$ is $\text{O}\left(\text{n}\right)$.
• $\text{4n}$ is also same as the $\text{O}\left(\text{n}\right)$ but larger than the $\text{3n+100logn}$ term because $\text{4n}$ term is higher than the $\text{3n}$ term.
• $\text{nlogn}$ belongs to order of $\text{O}\left(\text{n logn}\right)$