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)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jaidendutoit. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R70,00. You're not tied to anything after your purchase.
