Analysis of Algorithms

What about the Average Case?

• Idea:
• Assume that each of the n! permutations of A is equally likely.
• Compute the average over all possible different inputs of length N.
• Difficult to compute!
• In this course we focus on Worst Case Analysis!

• Analysis of Algorithms

See TimeComplexity Spreadsheet

• Analysis of Algorithms

What is “goodness”?

• Measure wall clock time
• Count operations
• Estimate Computational Complexity

• Analysis of Algorithms

• How can we quantify it?

• Correctness
• Minimum use of “time” + “space”

Asymptotic Analysis

• Analysis of Algorithms

• Uses a high-level description of the algorithm instead of an implementation
• Allows us to evaluate the speed of an algorithm independent of the hardware/software environment
• Estimate the growth rate of T(n)
• A back of the envelope calculation!!!

The idea

• Analysis of Algorithms

• Write down an algorithm
• Using Pseudocode
• In terms of a set of primitive operations
• Count the # of steps
• In terms of primitive operations
• Considering worst case input
• Bound or “estimate” the running time
• Ignore constant factors
• Bound fundamental running time

Growth Rate of Running Time

• Analysis of Algorithms

• Changing the hardware/ software environment
• Affects T(n) by a constant factor, but
• Does not alter the growth rate of T(n)
• The linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax