COMPENG 2SI4 Lecture Notes - Lecture 1: Linear Search, Binary Search Algorithm
8 Jan 2017
School
Department
Course
Professor
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.
