Class Notes
(787,679)

Canada
(482,834)

University of Waterloo
(17,977)

Computer Science
(744)

CS 341
(26)

Forbes Burkowski
(15)

Lecture

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

Lecture #2 - Runtime Analysis Fall 2009

Unlock Document

University of Waterloo

Computer Science

CS 341

Forbes Burkowski

Fall

Description

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