Analysis of Algorithms : An Active Learning Approach

1.4 RATES OF GROWTH 23 Big Theta We use θ( f ), called big theta, to represent the class of functions that grow at the same rate ...

24 ANALYSIS BASICS For each of the following pairs of functions f(n) and g(n), either f(n)=O(g(n)) or g(n)=O(f(n)), but not bot ...

1.5 DIVIDE AND CONQUER ALGORITHMS 25 for i = 1 to numberSmaller do DivideAndConquer(smallerSets[i], smallerSizes[i], smallSoluti ...

26 ANALYSIS BASICS In matching up the two algorithms, we see that the size limit in this case is 1, and our direct solution is t ...

1.5 DIVIDE AND CONQUER ALGORITHMS 27 Now that we have this generic formula, the answer to the question posed at the start of the ...

28 ANALYSIS BASICS the leaves. At each level, two elements are paired and the larger of the two gets copied into the parent node ...

1.5 DIVIDE AND CONQUER ALGORITHMS 29 tions, we need to know the absolute smallest number of operations needed to solve a particu ...

30 ANALYSIS BASICS leaf represents the worst case. The best case is the shortest path. The average case is the total number of e ...

1.5 DIVIDE AND CONQUER ALGORITHMS 31 This means that L, the minimum depth of the decision tree for sorting problems, is of order ...

32 ANALYSIS BASICS remainder = M mod N return GCD( N, remainder ) end if Give the recurrence relation for the number of multipli ...

1.6 RECURRENCE RELATIONS 33 The second is used if the direct solution is applied for a larger number of cases: These forms are e ...

34 ANALYSIS BASICS Now we begin to substitute back into the original equation. We will be care- ful not to simplify the resultin ...

1.6 RECURRENCE RELATIONS 35 indicates that we would have substituted five times, would have six terms based on
15, and would ha ...

36 ANALYSIS BASICS by 2, each of the subsequent equations will have half the value. This gives us the equations Now, we again su ...

1.6 RECURRENCE RELATIONS 37 have the direct case specified for n≤ 4, we can stop when we get to . Putting this together we get U ...

38 ANALYSIS BASICS 1.7 Analyzing Programs Let’s say that we have a large, complex program that takes longer to run than we want. ...

1.7 ANALYZING PROGRAMS 39 At the end of a program, these counters would tell us how many times each of the blocks of code in a s ...

This page intentionally left blank ...

Chapter 2 Searching and Selection Algorithms PREREQUISITES Before beginning this chapter, you should be able to Read and create ...

42 SEARCHING AND SELECTION ALGORITHMS STUDY SUGGESTIONS As you are working through the chapter, you should rework the examples t ...