Class Notes (787,679)
Canada (482,834)
CS 341 (26)

Lecture #2 - Runtime Analysis Fall 2009
Lecture #2 - Runtime Analysis Fall 2009

20 Pages
Unlock Document

University of Waterloo
Computer Science
CS 341
Forbes Burkowski

Analysis of Algorithms • We design algorithms to solve problems. – What are valid inputs for the problem? – What output should we get for each input? • An algorithm is correct if for every input it finds (computes) the correct output. – Running time. • The running time of algorithm A on input x is the time that algorithm A requires to derive the correct output given x. – Wewill denote this running tAme by R (x). – Weuse order notation to describe running time. – Note: We did not mention running time of the program for A. Running Time of an Instance • How to measure running time? – Wall-clock time is not a good measure, as it is different from computer to computer, e.g. 80386 vs. Pentium III. – Hence we remove details of the computer (exact speed of the processor, disk, memory, caching, etc.). – We count the number of elementary operations only. 1 Running Time of an Instance (cont.) – An elementary operation is an operation whose time can be bounded by a constant. It depends only on the implementation of the operation (either in hardware or software) and not on the inputs of the operation. Examples: • simple arithmeticoperations • simple comparisons • program flow control operations (if,goto) – Operations that are not elementary include: • maximumin an array of numbers • arithmeticoperations or comparisons of multi-precisionnumbers • concatenation of two strings • factorials Beware: many programming languages (such as perl) offer constructs that are not elementary operations Order notation 2 • E.g. quicksort runs in O(n ) time 30 25 running time 20 15 10 5 0 n = size of input (in bits) 1 35 7 9 11 13 15 – What it really means: 2 Many inputs for a given size n running time n inputsof inputsof inputsof length length one:length two: three: 0, 1 00, 01, 10, 1000, 001, …, 111 Worst case measure running time n • For each input size we select the worst case 3 Worst case measure running time n 0 1 2 3 4 5 6 7 8 Running time not monotonic running time n 4 Running time not monotonic running time n Actual running time may not be monotonic in n. But we consider the details of non-monotonic behaviour as needlessly complicated. Size of input is an integer running time n • Time function is only defined from integers to integers (N→N), we generalize to R→R 5 Easier to use a “simple” function Simplification ste:s 1. curvegoing throughbounding max times for each n. 2. Use monotonic bounding curve. 3. Use simple upper bounding curve. running time n 1 2 3 4 But what does n mean in this case? Size of input • Ideally: n is the number of bits used to code the input to the algorithm. • In practice: We consider the bit length of the various parameters specifying the problem. • Some examples: number of data items, number of vertices and edges, etc. • Cautionary note: – Be sure to understand that integers (decimal numbers) really have a bit length that goes up as the log of the integer value. – So, if execution time is dependent on the value of a parameter then we have an efficiency concern! 6 Worst Case and Complexity • The worst-case running time of an algorithm A is a function T(.) mapping n (the input size) to the longest running time for any input of size n. T (n) = Max{R (x) | |x| = n} A A • The time complexity of a problem is the running time of “the best” possible algorithm that solves the problem. Worst Case and Complexity • The average case running time is the expected running time on “average” data. – For some problems, it may be difficult to characterize what is meant by average data. T av( )= 1 ∑ R ( ). A {x: x = n {x:} =} • In this course we concentrate on worst case complexity. 7 Why use order notation? • Describes the run time performance of an algorithm without resorting to details about the environment on which the algorithm runs. – The analysis will not change with small “reasonable” changes in the instruction set or relative speed of individual instructions. • Thus it is widely applicable. – By counting in this looser fashion (ignoring details), we simplify our work in analysis. It has proven quite useful in practice. Definition of order notation f(n) is in O(g(n)) if there exist constants c > 0, and n0> 0 such that for all n > 0 , 0 < f(n) < cg(n). • Note: This definition properly says: f(n) is in O(g(n)), that is to say:f( )∈Ο(g n( ) the text uses the sloppier but more common form f(n) = O(g(n)). • IMPORTANT: O(g(n)) is really specifying aet of functions. 8 Definition of order notation • Using O(.) notation: – When used for an algorithm, it means the worst case running time is at most this large. – When used for a problem, it means the best known algorithm has this worst-case running time. Order notation (cont.) • You think you know it, but you may not… – It is often more subtle than it looks. – You should be able2to use the2definition to prove such things as n +3n∈Ο(n ) . – You should be comfortable with the notation and other functions that may be involved (e.g. log x). • Caution: – Although you might see an expression such as: 2 2 n +3n = O(n ), this is 2ot an equ2lity; in fact, it’s an implied inequality: n +3n < c n . • You cannot switch the two sides of the equation around. 9 More O-notation subtleties • Be sure that you understand the following: 2 – O(n+1), O(n +n), O(4n) are all technically correct, yet we do not use them. – We sim
More Less

Related notes for CS 341

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.