Welcome to Lesson 8!
Learning ObjectivesBy the end of this class, you should know...
 How to analyze the runtime and algorithmic runtime of algorithms
 What is Big O notation?
 What are Binary and Linear Search and how do we analyze their runtimes?
Announcements  Midterm 1 one week from today
 Study old quizzes, review exercises and your midterm review
 From Lesson 1  Lesson 8 (algorithm efficiency  no trees)
 Quiz 3 after the break
 Lab 4 due Monday
Review Activity With a partner, answer the following questions:  Define a recursive function, using the twopart definition given in class. A recursive function is one that _____________________ until _____________________
 Write the recursive bunnyEars and factorial functions.
Wrap Up Recursion Lesson
Recursive Binary Search
 Last quarter, you probably learned about Binary Search.
 Do you remember how Binary Search works?
 Conceptually, it is similar to the approach we might take to searching for a word in a dictionary or a name in a phone book.
 We might start in the middle of the book. If the name or word is on that page, then we are in luck and stop searching.
 Otherwise, if we land in the Ms and our word begins with an R, we know to look in the the second half of the book.
 If our word begins with an E, we know to look in the first half of the book.
 We can keep dividing our search space in half until we find the right word.
 Binary Search is typically performed on arrays, though can also be adapted to lists and other structures.
 In order to perform Binary Search, the array must be sorted into increasing order. Do you understand why?
 Below is a visual example of Binary Search in action on a sorted array.
 Below is the pseudocode for Binary Search.
 Where is/are the base case(s)?
 Where are the recursive function calls?
Pre: A[] is sorted in increasing order function binarySearch(A[1 ... n], value, low, high)
if high < low
return not found
mid := low + (highlow)/2; //the midpoint formula
if a[mid] := value
return mid
else if value < A[mid] //search the left half
return binarySearch(A, value, low, mid1)
else //search the right half
return binarySearch(A, value, mid+1, high)
Introduction to Algorithm Analysis  In computer science, there are multiple algorithms to accomplish the same goal.
 For example, think back to last class when we print a linked list in reverse both iteratively and recursively.
 Or consider that there are many, many algorithms for sorting a list.
 But, how do we know which algorithm is the best one to use?
 What are some metrics to compare different algorithms?
XKCD: Any one else have this problem?
Image Source. The goal of algorithm analysis is to provide a machineindependent comparison of algorithms to help us decide which ones are most efficient in terms of runtime and space used in memory (space complexity).
Growth Rate Analysis Example
 Let's do a more careful analysis of an algorithm to determine its growth rate.
 For example, take a look at the function below which prints a square to the console.
void printSquares(int n) { cout << "Printing " << n << " by " << n << " square\n"; for (int row = 1; row <= n; row++) { for (int col = 1; col <= n; col++) { cout << "*"; } cout << endl; } }
 First, lets count how many instructions (approximately) are given each time this function is called.
 For the sake of simplicity, we will assume that each statement requires only one instruction.
 Note that the number of assembly instructions required by each statement depends on both the language and the compiler.
 Thus, the reason for our simplification here and one reason we drop lower order terms and coefficents as discussed later in the lesson.
 Ignoring the looping behavior, we then get:
void printSquares(int n) { cout << "Printing " << n << " by " << n << " square\n"; //1 instruction for (int row = 1; row <= n; row++) //3 instructions { for (int col = 1; col <= n; col++) //3 instructions { cout << "*"; //1 instruction } cout << endl; //1 instruction } }
 However, some of these instructions are executed more than once when the function is called.
 In fact, the number of times these instructions are executed depends on the loops.
 For example, let's look at the cout << endl; statement. How many times is that statement executed?
 It will be executed each time the outer for loop is run.
 How many times does this loop run? Exactly n times.
 We can now say:
cout << endl; //n instructions
 What about the cout << "*"; statement?
 It will be executed each time the inner for loop is run. (n times)
 And, the inner for loop is executed each time the outer for loop is run. (n * n times)
 We can now say:
cout << "*"; //n^{2} instructions
 The initialization statements int row = 1 and int col = 1 each execute only once as part of their for loops. However, int col = 1 is also nested inside the outer for loop, making it execute n times.
 row <=n; row++; col <= n; and col++; are executed multiple times as part of their respective for loops.
 We can say:
for (int row = 1; row <= n; row++) //1 instruction + n instructions + n instructions
for (int col = 1; col <= n; col++) //n instructions + n^{2} instructions + n^{2} instructions
 We can now add these instructions up:
void printSquares(int n) { cout << "Printing " << n << " by " << n << " square\n"; //1 instruction for (int row = 1; row <= n; row++) //1 instruction + n instructions + n instructions { for (int col = 1; col <= n; col++) //n instructions + n^{2} instructions + n^{2} instructions { cout << "*"; //n^{2} instructions } cout << endl; //n instructions } }
 Combining like terms, we get the runtime function: 3n^{2 }+ 4n + 2
 To extract the growth rate we drop all non leading terms: 3n^{2 }+ 4n + 2 => 3n^{2}
 Then we drop the leading coefficient: 3n^{2} => n^{2.}
 This leaves us with the defining order of magnitude of the growth rate, n^{2}.
 Therefore, the resulting BigO runtime efficiency is shown as O(n^{2} ).
 Note that a quick look at the nested for loop could have led us to the same conclusion.
Introduction to RunTime Analysis  Runtime analysis is used to determine the efficiency of an algorithm and estimate its runtime.
 For example, sorting a large array of numbers can take seconds, hours or even years depending on the algorithm used.
 However, we can not simply use a stop watch to compare algorithms.
 The physical runtime will change depending on the speed of the processor used.
 Consider implementing an algorithm in C++ and then running the program on a super computer vs your grandma's old desktop from the 1980s.
 Instead, we are concerned with how the runtime of an algorithm scales mathematically as its input size increases.
 In other words, how well will an algorithm work if given a 10 element array vs a 10,000 element array vs a 1 million element array?
 We can represent an algorithm as a mathematical function of the input size of the problem.
 For example, to estimate the efficiency of an algorithm, we might count the number of steps in the algorithm.
 However, the number of steps in the algorithm is also dependent on the size of the problem.
 The algorithm can be carried out faster on a smaller problem and slower on a larger one.
 We can label the size of the problem n, where n is a variable to represent any problem size.
 After we calculate the steps in an algorithm, we can write what is called it's "runtime equation", which is a function written in terms of n.
 For example, a runtime equation might look like this: 4n^{2} + 2n + 1
 Once we know the runtime equation of an algorithm, we can use a mathematical metric for runtime ("BigO") to compare algorithms independent of hardware.
 The algorithm above has a "BigO" runtime of O(n^{2})
 We can compare this algorithm to other algorithms by comparing their "BigO" runtimes.
image source
 Space efficiency can also be measured this way, and may also be important, depending on resource constraints.
 In computer science we are less concerned with space efficiency.
Types of RunTime Analysis  When analyzing the runtime of an algorithm, we do so theoretically (remember, we are not interested in the performance on any specific machine).
 Specifically, we want to consider three possibilities:
 Best case  Given an input, the algorithm requires the least amount of computation, i.e. runs the fastest.
 Worst case  Given an input, the algorithm requires the most amount of computation, i.e. runs the slowest.
 Average case  Given an average case random input, provides a prediction about the average amount of computation, i.e. the average runtime.
 These are usually expressed as an order of magnitude in terms of "BigO".
image source
For Example:  Let's consider the algorithm linear search, which searches an array, indexbyindex, to find a specific value.
 If the item is in the array, we return the location index; otherwise, we return 1 (an impossible array index).
 Recall the code for linear search looks like this:
//Pre: array not empty int linearSearch(int array[], int valueToFind, const int SIZE) { for(int i = 0; i < SIZE; i++) {
if (array[i] == valueToFind) {
return i;
}
}
return 1;
}
 Let's consider the best case runtime for this algorithm. What if the array has 100 elements in it? What input would cause this algorithm to run for the least amount of time? (I am only looking for a verbal description here).
 What about the worst case?
 And the average case (what happens most of the time)?
Orders of Growth: BigO Notation
 BigO Notation is the mathematical formalism used in computer science to express how the runtime of an algorithm scales with input.
 We write BigO notation, like so:
O(growth rate function)  The growth rate function represents the leading term of the runtime equation. The leading term in a function is the term which has the greatest impact on the runtime of the algorithm.
 We typically express the growth rate function as a function of the input size, n. For example:
O(n) or O(n^{2}) or O(log(n))  The capital O stands for "of order".
 You can think of order here meaning of "the same general size."
 For example: A = O(n) means that the algorithm A is of order n.
 We could have another algorithm B = O(n).
 These are two different algorithms, but they have the same "order."
 In other words, they are considered to be equally efficient.
 We could also have a third algorithm C = O(n^{2}).
 This is a different algorithm with a different order.
 Algorithm C would be considered less efficient.
 The big O of A, B and C tells us that A and B grow at a very similar rate as input size increases, but that C grows faster (and will take longer to run).
Linear Search Example  Given our example above about linear search, we can express the best, worst and average case runtimes using big O notation:
Best case: 1 > O(1) // We found the item on the first try.
Worst case: n > O(n) // We have to search all n nodes in the list to find the item.
Average case: n/2 > O(n) // We have to search an average of half of the n nodes in the list to find the item.
But wait! Shouldn't that be O(n/2)?
 Note that when we express the order of magnitude, we drop any lesser terms and coefficients on our variables.
 These lesser terms and coefficients are considered insignificant in comparison to the growth rate function (the highest order term).
 The lesser terms and coefficients have little impact on the overall efficiency of the algorithm.
 So, for the average case above, you might think you should express it as O(n/2). However, since we drop coefficients, we write it simply as O(n).
Another Example  As another example, if we know the the runtime of a specific algorithm in its worst case is:
f(n) = 3n^{4} + 100n^{2} + 10n + 50
We would express its order of magnitude as O(n^{4}).
f(n) = 3n^{4} + 100n^{2} + 10n + 50 = O(n^{4})
Note the use of the equals sign above.
Some Common Orders of Magnitude
 O(1) is called bounded or constant time. The amount of work is bounded by a constant and does not depend on the size of the problem.
 For example: Assigning a value to a single index of an array is O(1).
 O(log_{2} n) is called logarithmic time. The amount of work depends on the log of the size of the problem. Algorithms that successively cut the amount of data to be processed in half typically fall into this category.
 For example: Binary search (as we shall discuss in a moment) and other "Divide and Conquer" algorithms.
 O(n) is called linear time. The amount of work is typically some constant times the size of the problem.
 For example: Printing each element in a list of n elements. Or, searching a list of unordered elements, as we saw in the linear search example above.
 O(nlog2 n) is called (for lack of a better term) nlog(n) time. Algorithms of this type typically involve applying a logarithmic time algorithm n times  such as applying a logarithmic algorithm to all n items in a list.
 For example: The better sorting algorithms such as Quicksort, Heapsort and Mergesort.
 O(n^{2}) is called quadratic time. Algorithms of this type typically involve applying a linear algorithm n times. They also typically have a nested loop structure, such as a nested for loop.
 For example, most simple sorting algorithms are O(n2).
 O(2^{n}) is called exponential time. These algorithms are costly, as the exponential times increase dramatically in relation to the size of n. They should only be used on very small data sets or not at all.
 For example, our recursive fibonacci function from the previous class is approximately O(2^{n}), since for each of the n inputs, we broke the problem into two recursive calls.
 O(n!) is called factorial time. These algorithms are even more costly and can involve what is called "brute force" solutions (rather than efficient, wellthoughtout solutions).
 For example, a bruteforce solution to the Traveling Salesman Problem (which you will probably learn more about in Discrete Math).
Graphical Comparison of Common Orders of Magnitude
Image source.
Numerical Comparison of Rates of Growth Input  1
 log n
 n
 nlogn
 n^{2}  2^{n}  1
 1  0
 1  0
 1  2
 2  1  1  2  2  4  4  4  1  2  4  8  16  16  8  1  3  8  24  64  256
 16  1  4  16  64  256  65,536
 32  1  5  32  160  1,024  4,294,967,296  64  1  6  64  384  4,096  About a month of instructions on a supercomputer
 128  1  7  128  896  16,384  About 10^{12} times greater than the age of the universe in nanoseconds
 256  1  8  256  2,048  65,536  Don't ask

Review of Linear Search RunTime
 We saw when we analyzed Linear Search that it add the following runtimes:
 Best Case: O(1)
 Average Case: O(n)
 Worst Case: O(n)
 Thus, we consider Linear Search to be an O(n) algorithm.
 A brief examination of its code reveals confirms it as an O(n) algorithm because it has a for loop that goes through all n elements in the array.
int linearSearch(int array[], int value, const int SIZE) {
for(int i = 0; i < SIZE; i++) < single loop generally indicates an O(n)algorithm {
if (array[i] == value) {
return i;
}
}
return 1;
}
Binary Search RunTime But, what about a search algorithm that we know to be faster: binary search?
 How can we analyze its best, worst and average case runtimes?
 In binary search, we continually divide the search space in half (k times) until it contains only one element:
n > n / 2 > n / 4 > n/ 8... > n/ 2^{k} = 1  Multiply both sides by 2^{k}
n = 2^{k}  Then take the log of both sides:
log_{2} (n) = k  This leaves us with O(log_{2} n) (also written in BigO notation as O(log n))
 To verify, let's look at an example involving the worst case...
 How many times did we have to split the array in half before it "became empty"?
 It took us 4 passes.
 In general, we can split an array in half floor(log_{2}(n)) + 1 times before it becomes empty.
 Recall that log_{base} value = exp is equivalent to base^{exp} = value
 Or, log_{b} a = c is equivalent to b^{c} = a.
 In our example with 15 elements, we needed 4 comparisons in the worst case.
 floor(log_{2}(15)) + 1 = 3 + 1 = 4 <The formula works!
 Therefore, Binary Search is O(log_{2} n) in the worst case. (Remember that we drop the + 1).
 For algorithms that are log_{2} n, each time you double the number the number of elements in the array or other structure, the amount of work you do increases by just one unit.
Binary Search Pays Off!
Number of Elements Number of Comparisons _______________________________________________________ 15 4 31 5 63 6 127 7 255 8 511 9 1023 10
1 million 20
 This is a very significant savings over linear search. However, binary search requires a sorted array , whereas linear search does not. If we need to sort the array before applying the binary search algorithm, there will be a loss of efficiency.
Binary Search Average and Best Case
 The average case of binary search is also O(log_{2} n) as it takes on average one fewer comparison than in the worst case.
 What is the best case?
Linear vs Binary Search Recap: Linear and Binary Search Best, Average and Worst Case
Linear Search Binary Search
Best : O(1) O(1)
Average: O(n) O(log_{2} n)
Worst: O(n) O(log_{2} n)
Analysis of Algorithms Practice Find a partner and discuss the following: What is the BigO runtime of the below functions?
A. void List:print() { NodeRef temp = head; while (temp != NULL)
{
cout << temp>data << " ";
temp = temp>next;
}
cout << endl;
}
B.
void bubble_sort(int arr[], int n) { for (int i = 0; i < n; ++i) {
for (int j = 0; j < n  i  1; ++j) {
if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } cout << "The array contents are:"<< endl;
for(int k = 0; k < n; k++)
{ count << "Element " << k << " is " << arr[k] << endl;
} }
C. void mysteryFunction(int n) { int i = 0; while (i < n)
{ for (int j = 0; j < n; j++)
{
for (int k = 0; k < n/2; k++)
{
if (j < k && k > i)
cout << "*";
}
cout << endl;
}
i++
}
}
Wrap Up  With your partner, answer the learning objective questions from the beginning of the lesson.
Upcoming Assignments  Lab 4 due next class
 Midterm 1 on Wednesday
