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

64 views2 pages

Published on 8 Jan 2017

Department

Computer Engineering

Course

COMPENG 2SI4

Professor

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

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