Lecture 6 - May 23, 2013
Chapter 4– Algorithm Analysis
Algorithm: It is a sequence of well-define steps for solving a given problem.
Inputs -> Algorithm -> Outputs
For a problem P, we may have multiple algorithms. For every algorithm A, we may havemultiple
implementations. How do we assess the efficiency of A?
Experimentation
• Implement and run
• Influenced by processor, memory, OS, complier, PL…
• You cannot test for all inputs
Complexity Analysis (pencil and paper approach)
• Examine the algorithm
• Implementation independent
• Considers all input instances
Example: Write an algorithm to find the sum of the first n numbers
Solution 1: Solution 2:
Random Access Machine (RAM) Model
• Memory accesses take constant time
• Primitive operations take constant time
o Comparisons
o Arithmetic operations
o Assignment
Measuring Time Complexity
• Given the size of input n
• Sum the number of memory accesses
• Sum the number of primitive operations in the algorithm
• Derive a formula T(n)
T(n) is approximately the number of steps in the algorithm in terms of the input size. Analysis Types
• Worst case – most common approach, simpler, crucial
• Best case – Almost always faster on certain inputs
• Average case – difficult
Big-O Notation (AsymptoticNotation)
• Approximates time complexity of algorithms
• Given a function T(n), T(n) is O(f(n))
if there exists a function f(n) such that T(n) ≤ c.f(n) for some c > 0 and some m > 0, n ≥ m
where m is a sufficiently large value for n.
T(n) = 1 + n + 1
= n + 2
T(n) is O(f(n)) – T(n) is bounded from above by f(n)
Determining the time complexity
Considerations when calculating T(n)
• Most interested in the dominant term
• Group together similar expressions
• For a loop
- Determine the # of iterations
T(n) = 1

More
Less