Chapter 4.1 PERFORMANCE:
Mantra for this chapter: Pay attention to the cost
We apply mathematical analysis to derive concise models of the cost - the experiments we
design must be reproducible and falsifiable
How are the experiments done? We can simply run a program on various inputs, measuring
the amount of time to process each input.
Observations:
1. is a problem size that characterizes the difficulty of the computational task.
Normally, the problem size is either the size of the input or the value of a command-
line argument. Intuitively, the running time should increase with the problem size –
interested in how much it increases by.
2. Running time is relatively insensitive to the input itself; it depends primarily on the
problem size
Proper analysis involves:
- Detailed understanding of the program
- Detailed understanding of the system and the computer
- Advanced tools of mathematical analysis
Doubling hypothesis -> What is the effect on the running time of doubling the size of the
input?
Mathematical analysis:
the total running time is determined by two primary factors:
- The cost of executing each statement (property of the system)
- The frequency of execution of each statement (property of the algorithm)
We write ~f(n) to represent any quantity that, when divided by f(n), approaches 1 as n
grows. We also write g(n) ~ f(n) to indicate that g(n)/f(n) approaches 1 as n grows.
We focus on the instructions that are executed most frequently = inner loop
For many programs: the running time satisfies the relationship T(n) ~ cf(n) where c is a
constant and f(n) is a function known as the order of growth of the running time = simple
but powerful model of running time. With these approximations, the particular machine
that you are using does not play a significant role in the models—the analysis separates the
algorithm from the system (algorithm determines the order of growth)
Mantra for this chapter: Pay attention to the cost
We apply mathematical analysis to derive concise models of the cost - the experiments we
design must be reproducible and falsifiable
How are the experiments done? We can simply run a program on various inputs, measuring
the amount of time to process each input.
Observations:
1. is a problem size that characterizes the difficulty of the computational task.
Normally, the problem size is either the size of the input or the value of a command-
line argument. Intuitively, the running time should increase with the problem size –
interested in how much it increases by.
2. Running time is relatively insensitive to the input itself; it depends primarily on the
problem size
Proper analysis involves:
- Detailed understanding of the program
- Detailed understanding of the system and the computer
- Advanced tools of mathematical analysis
Doubling hypothesis -> What is the effect on the running time of doubling the size of the
input?
Mathematical analysis:
the total running time is determined by two primary factors:
- The cost of executing each statement (property of the system)
- The frequency of execution of each statement (property of the algorithm)
We write ~f(n) to represent any quantity that, when divided by f(n), approaches 1 as n
grows. We also write g(n) ~ f(n) to indicate that g(n)/f(n) approaches 1 as n grows.
We focus on the instructions that are executed most frequently = inner loop
For many programs: the running time satisfies the relationship T(n) ~ cf(n) where c is a
constant and f(n) is a function known as the order of growth of the running time = simple
but powerful model of running time. With these approximations, the particular machine
that you are using does not play a significant role in the models—the analysis separates the
algorithm from the system (algorithm determines the order of growth)
