Welcome to Lesson 8!

Learning Objectives
By the end of this class, you should know...
  • How to analyze the run-time and algorithmic run-time of algorithms
  • What is Big O notation?
  • What are Binary and Linear Search and how do we analyze their run-times?

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 two-part 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 + (high-low)/2; //the midpoint formula if a[mid] := value return mid else if value < A[mid] //search the left half return binarySearch(A, value, low, mid-1) else //search the right half return binarySearch(A, value, mid+1, high)

  • You will be writing recursive binary search as part of your Lab 4.

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?

Efficiency

Image Source.
  • The goal of algorithm analysis is to provide a machine-independent comparison of algorithms to help us decide which ones are most efficient in terms of run-time 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 << "*"; //n2 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 + n2 instructions + n2 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 + n2 instructions + n2 instructions
    {
    cout << "*"; //n2 instructions
    }
    cout << endl; //n instructions
    }
}
  • Combining like terms, we get the run-time function: 3n2 + 4n + 2
  • To extract the growth rate we drop all non leading terms: 3n+ 4n + 2   =>   3n2
  • Then we drop the leading coefficient: 3n2   =>   n2.
  • This leaves us with the defining order of magnitude of the growth rate,   n2.
  • Therefore, the resulting Big-O run-time efficiency is shown as   O(n2 ).
  • Note that a quick look at the nested for loop could have led us to the same conclusion.


Introduction to Run-Time Analysis

  • Run-time analysis is used to determine the efficiency of an algorithm and estimate its run-time.
  • 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 run-time 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 run-time 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 "run-time equation", which is a function written in terms of n.
    • For example, a run-time equation might look like this: 4n2 + 2n + 1
  • Once we know the run-time equation of an algorithm, we can use a mathematical metric for run-time ("Big-O") to compare algorithms independent of hardware.
    • The algorithm above has a "Big-O" run-time of O(n2)
    • We can compare this algorithm to other algorithms by comparing their "Big-O" run-times.

enter image description here

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 Run-Time Analysis

  • When analyzing the run-time 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 run-time.
  • These are usually expressed as an order of magnitude in terms of "Big-O".

image source


For Example:

  • Let's consider the algorithm linear search, which searches an array, index-by-index, 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 run-time 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: Big-O Notation

  • Big-O Notation is the mathematical formalism used in computer science to express how the run-time of an algorithm scales with input.
  • We write Big-O notation, like so:

O(growth rate function)

  • The growth rate function represents the leading term of the run-time equation. The leading term in a function is the term which has the greatest impact on the run-time of the algorithm.
  • We typically express the growth rate function as a function of the input size, n. For example:
O(n) or O(n2) 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(n2).
  • 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 run-times 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 run-time of a specific algorithm in its worst case is:
f(n) = 3n4 + 100n2 + 10n + 50

We would express its order of magnitude as O(n4).

f(n) = 3n4 + 100n2 + 10n + 50 = O(n4)

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(log2 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(n2) 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(2n) 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(2n), 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, well-thought-out solutions).
    • For example, a brute-force 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

 Input1
 log n
n
nlogn
 n2 2n
1
 10
 10
 12
 2 1 1 2 2 4 4
 4 1 2 4 8 16 16
 8 1 3 8 24 64256
 16 1 4 16 64 25665,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 super-computer
 128 1 7 128 896 16,384 About 1012 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 Run-Time

  • We saw when we analyzed Linear Search that it add the following run-times:
    • 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 Run-Time
  • But, what about a search algorithm that we know to be faster: binary search?
  • How can we analyze its best, worst and average case run-times?
  • 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/ 2k = 1
  • Multiply both sides by 2k
n = 2k
  • Then take the log of both sides:
log2 (n) = k
  • This leaves us with O(log2 n) (also written in Big-O 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(log2(n)) + 1 times before it becomes empty.
  • Recall that logbase value = exp is equivalent to baseexp = value
  •  Or, logb a = c is equivalent to bc = a.
  • In our example with 15 elements, we needed 4 comparisons in the worst case.
  • floor(log2(15)) + 1 = 3 + 1 = 4 <--The formula works!
  • Therefore, Binary Search is O(log2 n) in the worst case. (Remember that we drop the + 1).
  • For algorithms that are log2 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(log2 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(log2 n)

Worst:                O(n)                                    O(log2 n)


Analysis of Algorithms Practice
Find a partner and discuss the following: What is the Big-O run-time 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