School

McMaster UniversityDepartment

Computer EngineeringCourse Code

COMPENG 2SI4Professor

Sorina DumitrescuLecture

1This

**preview**shows half of the first page. to view the full**2 pages of the document.**Why Algorithm Analysis

● Allows us to write efficient programs

○ Programs that uses time and memory without wasting it

● The most simple way to analyse an algorithm is to implement it and then compare the

resource utilization

○ This is a very time consuming technique

○ Also it is very difficult to choose fair test cases for each algorithm

Algorithm Runtime

● We assume that all the basic operations in a program are done sequentially and

individually

○ Basic operations: assignments, arithmetic operations, and comparison

● We assume that each operation takes the same amount of time to complete and so the

total runtime is proportional to the number of operations

Best, Worst and Average Case

● Best case → shortest run time for all possible inputs of n

● Average case → average run time for all possible inputs of n

○ Requires knowledge of what inputs are most likely

● Worst Case → largest runtime for all possible inputs of n

○ Guarantees a level of performance

○ Analysis is easier

Asymptotic Analysis

● We need to get essential information for run time as n becomes large

● We do not need to be too precise when doing this analysis

○ We focus on the dominant terms of T(n) and ignore the constants

● Two compare two algorithms we divide one by the other and find the infinite limit

● Ex: �

�

○ If the limit approaches infinity then F(n) is growing faster than G(n)

○ If the limit is 0 then G(n) is growing faster than F(n)

○ If the limit is a constant then the growth rates are equal

● Functions are grouped using their complexity classes → functions with the same run

time are in the same class

Asymptotic Notation

find more resources at oneclass.com

find more resources at oneclass.com

###### You're Reading a Preview

Unlock to view full version