Analysis of Algorithm we only analyze correct algorithms, Incorrect algorithms (Might not halt at all on some input instances, Might halt with other than the desired answer), Analyzing an algorithm (Predicting the resources that the algorithm requires, Resources include). | Nguyen Viet Anh - CS3329 Spring 2011 Algorithm Analysis We only analyze correct algorithms An algorithm is correct If, for every input instance, it halts with the correct output Incorrect algorithms Might not halt at all on some input instances Might halt with other than the desired answer Analyzing an algorithm Predicting the resources that the algorithm requires Resources include Memory Communication bandwidth Computational time (usually most important) Nguyen Viet Anh - CS3329 Spring 2011 Algorithm Analysis Factors affecting the running time computer compiler algorithm used input to the algorithm The content of the input affects the running time typically, the input size (number of items in the input) is the main consideration . sorting problem the number of items to be sorted . multiply two matrices together the total number of elements in the two matrices Machine model assumed Instructions are executed one after another, with no concurrent operations Not parallel computers Nguyen Viet Anh - CS3329 Spring 2011 Example Calculate N i3 i 1 1 1 2 2N+2 3 4N 4 1 Lines 1 and 4 count for one unit each Line 3: executed N times, each time four units Line 2: (1 for initialization, N+1 for all the tests, N for all the increments) total 2N + 2 total cost: 6N + 4 O(N) Nguyen Viet Anh - CS3329 Spring 2011 Worst- / average- / best-case Worst-case running time of an algorithm The longest running time for any input of size n An upper bound on the running time for any input guarantee that the algorithm will never take longer Example: Sort a set of numbers in increasing order; and the data is in decreasing order The worst case can occur fairly often . in searching a database for a particular piece of information Best-case running time sort a set of numbers in increasing order; and the data is already in increasing order Average-case running .
