Class Notes (839,124)
CS 234 (31)
Lecture

# notes06a.pdf

4 Pages
125 Views

Department
Computer Science
Course Code
CS 234
Professor
Robert Sproule

This preview shows page 1. Sign up to view the full 4 pages of the document.
Description
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

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.