Class Notes (1,019,315)
CA (585,447)
McMaster (47,718)
COMPENG (55)
Lecture 1

COMPENG 2SI4 Lecture Notes - Lecture 1: Linear Search, Binary Search AlgorithmPremium

2 pages61 viewsWinter 2017

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

This 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

Subscribers Only

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.