Asymptotic Analysis of Algorithms

Asymptotic Analysis of Algorithms
Chapter 4

Overview
• Motivation • Definition of Running Time • Classifying Running Time • Asymptotic Notation & Proving Bounds • Algorithm Complexity vs Problem Complexity

Overview
• Motivation • Definition of Running Time • Classifying Running Time • Asymptotic Notation & Proving Bounds • Algorithm Complexity vs Problem Complexity

The Purpose of Asymptotic Analysis
• To estimate how long a program will run. • To estimate the largest input that can reasonably be given to the program. • To compare the efficiency of different algorithms. • To help focus on the parts of code that are executed the largest number of times. • To choose an algorithm for an application.

Overview
• Motivation • Definition of Running Time • Classifying Running Time • Asymptotic Notation & Proving Bounds • Algorithm Complexity vs Problem Complexity

Running Time

• Most algorithms transform input objects into output objects.
• The running time of an algorithm typically grows with the input size.
• Average case time is often difficult to determine.
• We focus on the worst case running time.
– Easier to analyze
– Reduces risk

Running Time

120 100
80 60 40 20
0 1000

best case average case worst case

2000

3000

Input Size

4000

Experimental Studies

• Write a program implementing the algorithm
• Run the program with inputs of varying size and composition
• Use a method like System.currentTimeMillis() to get an accurate measure of the actual running time
• Plot the results

Time (ms)

9000 8000 7000 6000 5000 4000 3000 2000 1000
0 0

50

100

Input Size

Limitations of Experiments
• It is necessary to implement the algorithm, which may be difficult
• Results may not be indicative of the running time on other inputs not included in the experiment.
• In order to compare two algorithms, the same hardware and software environments must be used

Theoretical Analysis
• Uses a high-level description of the algorithm instead of an implementation
• Characterizes running time as a function of the input size, n.
• Takes into account all possible inputs • Allows us to evaluate the speed of an algorithm
independent of the hardware/software environment

Primitive Operations

• Basic computations performed by an algorithm

• Examples:

• Identifiable in pseudocode
• Largely independent from the programming language

– Evaluating an expression
– Assigning a value to a variable

• Assumed to take a constant amount of time

– Indexing into an array
– Calling a method

– Returning from a method