In this lecture we learned about: Overriding a method, static and dynamic binding, virtual function, types of member function, abstract method/ abstract class, constructor and destructor : virtual or non-virtual. | Lecture 15 Recap Overriding a Method Static and Dynamic Binding Virtual Function Types of Member Function Abstract Method/ Abstract Class Constructor and Destructor : Virtual or Non-Virtual Chapter 6 Algorithm Analysis Introduction In this chapter, we study how to estimate the time required for an algorithm how to use techniques that drastically reduce the running time of an algorithm how to use a mathematical framework that more rigorously describes the running time of an algorithm how to write a simple binary search routine Definition An algorithm is a clearly specified set of instructions a computer follows to solve a problem Once an algorithm is given for a problem and determined to be correct, the next step is to determine the amount of resources, such as time and space, that the algorithm will require. This step is called algorithm analysis An algorithm that requires several gigabytes of main memory is not useful for most current machines, even if it is completely correct Algorithm Analysis The amount of time that any algorithm takes to run almost always depends on the amount of input that it must process For instance: sorting 10,000 elements requires more time than sorting 10 elements The running time of an algorithm is thus a function of the input size The exact value of the function depends on many factors, such as the speed of the host machine, the quality of the compiler, and in some cases, the quality of the program. For a given program on a given computer, we can plot the running time function on a graph Example 1: The curves represent four common functions encountered in algorithm analysis: Linear O(N log N) Quadratic Cubic The input size N ranges from 1 to 100 items, and the running times range from 0 to 10 milliseconds A quick glance at Figure suggests that the linear, O(N log N), quadratic, and cubic curves represent running times in order of decreasing preference Example 2: Problem of Downloading a File from the Internet Suppose that there is an | Lecture 15 Recap Overriding a Method Static and Dynamic Binding Virtual Function Types of Member Function Abstract Method/ Abstract Class Constructor and Destructor : Virtual or Non-Virtual Chapter 6 Algorithm Analysis Introduction In this chapter, we study how to estimate the time required for an algorithm how to use techniques that drastically reduce the running time of an algorithm how to use a mathematical framework that more rigorously describes the running time of an algorithm how to write a simple binary search routine Definition An algorithm is a clearly specified set of instructions a computer follows to solve a problem Once an algorithm is given for a problem and determined to be correct, the next step is to determine the amount of resources, such as time and space, that the algorithm will require. This step is called algorithm analysis An algorithm that requires several gigabytes of main memory is not useful for most current machines, even if it is completely correct .
