Premium

School

McMaster University
Department

Computer Engineering

Course Code

COMPENG 2SI4

Professor

Sorina Dumitrescu

Lecture

1

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

Over 90% improved by at least one letter grade.

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.