Algorithm Analysis
with
Big Oh
Data Structures and Design with Java and JUnit
Chapter 12
©Rick Mercer
, Algorithm Analysis
w Objectives
⎯ Analyze the efficiency of algorithms
⎯ Analyze a few classic algorithms
• Linear Search, Binary Search, Selection Sort
⎯ Know the differences between O(1), O(n),
O(log n), and O(n2)
⎯ Visualize runtime differences with
experiments
, Algorithms continued
w Computer Scientists focus on problems such as
⎯ How fast do algorithms run
⎯ How much memory does the process require
w Example Applications
⎯ Make the Internet run faster
• Pink-Degemark's routing algorithms
• Gene Meyers determined the sequences of the Human
genome using his whole genome shotgun algorithm
, Analysis of Algorithms
w We have ways to compare algorithms
⎯ Generally, the larger the problem, the longer it
takes the algorithm to complete
⎯ Sorting 100,000 elements can take much more
time than sorting 1,000 elements
• and more than 10 times longer
⎯ the variable n suggests the "number of things"
⎯ If an algorithm requires 0.025n2 + 0.012n +
0.0005 seconds, just plug in a value for n
with
Big Oh
Data Structures and Design with Java and JUnit
Chapter 12
©Rick Mercer
, Algorithm Analysis
w Objectives
⎯ Analyze the efficiency of algorithms
⎯ Analyze a few classic algorithms
• Linear Search, Binary Search, Selection Sort
⎯ Know the differences between O(1), O(n),
O(log n), and O(n2)
⎯ Visualize runtime differences with
experiments
, Algorithms continued
w Computer Scientists focus on problems such as
⎯ How fast do algorithms run
⎯ How much memory does the process require
w Example Applications
⎯ Make the Internet run faster
• Pink-Degemark's routing algorithms
• Gene Meyers determined the sequences of the Human
genome using his whole genome shotgun algorithm
, Analysis of Algorithms
w We have ways to compare algorithms
⎯ Generally, the larger the problem, the longer it
takes the algorithm to complete
⎯ Sorting 100,000 elements can take much more
time than sorting 1,000 elements
• and more than 10 times longer
⎯ the variable n suggests the "number of things"
⎯ If an algorithm requires 0.025n2 + 0.012n +
0.0005 seconds, just plug in a value for n
