Chapter 14, Problem 15RE

Explanation of Solution

Order of growth:

• Order of growth is used to indicate the amount of time taken by a program based on the size of the input that is provided.
• It is used to indicate how the program will behave as the order of size of the input being increased.
• It is also known to be a function of size of its input and the function is represented in the form of Big O notation that is in the form “$\text{O}\left(\right)$”.

Some of the time complexities:

The below are some of the time complexities and they are:

• Constant running time $\text{O}\left(1\right)$
• Linear running time $\text{O}\left(\text{n}\right)$
• Logarithmic running time $\text{O}\left(\text{log}\text{n}\right)$
• Log-linear running time $\text{O}\left(\text{n}\text{log}\text{n}\right)$
• Polynomial running time