Class Notes (970,163)
CA (574,167)
McMaster (51,674)
COMPENG (55)
Lecture 1

COMPENG 2SI4 Lecture 1: Algorithm Analysis Premium

by OneClass502226 , Winter 2017
2 Pages
58 Views
Winter 2017

Department
Computer Engineering
Course Code
COMPENG 2SI4
Professor
Sorina Dumitrescu
Lecture
1

This preview shows half of the first page. Sign up 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

Loved by over 2.2 million students

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
Description
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
More Less

Only half of the first page are available for preview. Some parts have been intentionally blurred.

Unlock Document

Unlock to view full version

Unlock Document

You've reached the limit of 4 previews this month

Create an account for unlimited previews.

Notes
Practice
Earn
Me

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.