Running Time Algorithm Running Time Analysis Why do we need to analyze the running time of a program Option 1 Run the program and time it Why is this option bad What can we do about it Pseudo Code Used to specify algorithms Part English part code Math Review Summation Sum of n consecutive digits n n 1 2 Algorithm arrayMax A n curMax A 0 for i 1 i n i if curMax A i curMax A i return curMax Counting Operations Asymptotic Notation Algorithm arrayMax A n curMax A 0 1 for i 1 i n i n 1 or 2 if curMax A i curMax A i return curMax 1 2n 2 n 5 12 n 100 202 n 1 000 000 2 000 002 Best case n 2 Worst case 2n 2 Average case hard to analyze Running time grows proportionally to n What happens as n gets large 1 Big Oh Examples f n is O g n if there is a real constant c 0 and an integer constant n0 1 such that f n cg n for every integer n n0 87n4 7n 2n 2 is O n n0 1 c 3 4n 4 7n3logn 3nlogn 12logn Terminology Logarithmic O logn Linear O n Linearithmic O nlogn Quadratic O n2 Polynomial O nk k 1 Exponential O an a 1 Example Example 4 n 1 2 12 3 9 n 1 5 8 1 Find maximum number in nxn matrix Algorithm Another Example 0 n 1 2 What is the big oh running time of this algorithm Algorithm Input A n curMax A 0 0 for i 0 i n i for j 0 j n j if curMax A i j curMax A i j return curMax 0 6 0 0 6 4 8 n 1 3 6 Determine how many elements of array 1 match elements of array 2 Algorithm 2 Another Example 0 2 4 n 1 6 0 6 8 n 1 3 Algorithm Input A B n for i 0 i n i for j 0 j n j if A i A j matches break What is the running time of the algorithm 3
View Full Document
Unlocking...