Chapter Two

Chapter 2.1 and 2.2 In section 2.1 the chapter defines and discusses the importance of efficiency. It goes through three different definitions of an efficient algorithm, highlighting its strengths and flaws. It also goes over worst-case running time and brute force searches, and how worst-case running time gives an accurate capturing of the efficiency of a problem. In section 2.2, the chapter directly goes deeper into defining the running-time of a problem, such as the asymptotic upper bound, asymptotic lower bound, and the tight bound. Lastly, 2.2 covers the different properties of the upper and lower bounds, such as the transitive property and the sums of functions property, and covers three common functions of the asymptotic bounds (polynomial, logarithmic, and exponential).