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

64 views2 pages
user avatar
Published on 8 Jan 2017
School
McMaster University
Department
Computer Engineering
Course
COMPENG 2SI4
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
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Document Summary

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. 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 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. 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.