tailieunhanh - Lecture ECE 250 - Algorithms and data structures: Algorithm analysis

In this topic, we will examine code to determine the run time of various operations. We will introduce machine instructions, we will calculate the run times of: operators +, -, =, +=, ++, etc; control statements if, for, while, do-while, switch; functions; recursive functions. | 50 WATERLOO ENGINEERING University of Waterloo O Algorithm Analysis m Harder . L ctrical and Computer El Xada VATERLO ENGINEERING 77 Xf P Asymptotic Analysis 2 Outline In this topic we will examine code to determine the run time of various operations We will introduce machine instructions We will calculate the run times of Operators - etc- - Control statements if for while do-while switch - Functions - Recursive functions VATERLO ENGINEERING 77 Xf P Asymptotic Analysis 3 Motivation The goal of algorithm analysis is to take a block of code and determine the asymptotic run time or asymptotic memory requirements based on various parameters - Given an array of size n Selection sort requires 0 n2 time Merge sort quick sort and heap sort all require Q n ln n time - However Merge sort requires 0 n additional memory Quick sort requires 0 ln n additional memory Heap sort requires 0 1 .