# Asymptotic Analysis of Algorithms

Download Asymptotic Analysis of Algorithms

## Preview text

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

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

## Categories

## You my also like

### The Efficiency of Algorithms and Big O Notation

200.9 KB10.6K2.2K### Universite Paris Sorbonne / Ircam Paris

35.2 MB2K581### SIMPLIFIED MUSIC NOTATION INSTRUCTIONS – THE SYMBOLS

387.1 KB79.3K12.7K### Assignment 1: Set theory, Relations, Functions

17.6 KB20K8.8K### Electron Configuration Worksheet Name: VandenBout/LaBrake

71.2 KB18.1K6.9K### Proposed Approach of Extended Johnson Algorithm Analysis for

241.3 KB5.2K929### Performance Analysis of Floyd Warshall Algorithm vs

389.4 KB19.8K3K### Performance Evaluation Of Operating Systems Scheduling Algorithms

1.4 MB7.8K2.6K### Lecture 23: Measuring and Analysing Algorithm Complexity

228.5 KB37.2K5.2K