Before reading section 2.4, go review section 1.4.2 which covers the bisection algorithm. This is an algorithm you should already know, but familiarize yourself with the notation this book uses.
Then, read section 2.4 of the textbook and answer these questions on Gradescope.
- Section 2.4.2 compares the complexities of four functions, which they describe as “bad”. What they mean here is they are each extremely fast growing. Consider any one of the four functions, I’ll call it f(n). If f(n) describes the time it takes for some algorithm to execute on an input of size n (think: an array of length n), what point is this portion of the textbook trying to make about n? Try to relate your answer to the algorithm mentioned in the previous sentence.
- Refer back to the definitions at the beginning of this section (increasing, decreasing, nondecreasing, nonincreasing, monotone, converges, bounded). Which of these apply to one or more of the functions in the table in section 2.4.2 ? Explain your reasoning.
