Chapter 4, Problem 8R

Explanation of Solution

Asymptotic growth rate:

According to asymptotic growth rate, the 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 is ordered from least to greatest based on the asymptotic functions.

• “$2^{10}$” is the constant time so, it is ordered first.
• Next, “${\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)$”