CS61B 2018 Lecture 18 Asymptotics II: Analysis of Algorithms + disc08: More Asymptotic Analysis

[poanc]

Summary

• A first example with Loops
• Loop Example 2
• Example 3: A Basic Recurrence
  • The Intuitive Method
  • The Algebraic Method
  • Recurrence Relations
• Example 4 : Binary Search
• Example 5 : Merge Sort
  • arbitrary unit of time
• Summary
• disc08: More Asymptotic Analysis

A first example with Loops

Loop Example 2

There is no magic shortcut :(

It would be really nice if there were some magic way to look at an algorithm and just know its runtime. It would be super convenient if all nested for loops were N^2​ . They're not. And we know this because we just did two nested for loop examples above, each with different runtimes.

In the end, there is no shortcut to doing runtime analysis. It requires careful thought. But there are a few useful techniques and things to know.

Sum Things to Know Here are two important sums you'll see quite often, and should remember:

Example 3: A Basic Recurrence

In this course, there three methods to figure out or calculate the Big Theta:

1. The Intuitive Method
2. The Algebraic Method
3. Recurrence Relations

The Intuitive Method

The Algebraic Method

The second way to approach this problem is to count the number of calls to f3

Recurrence Relations

We can use a "recurrence relation" to count the number of calls, instead of an algebraic approach.

Binary Search

Binary search is a nice way of searching a list for a particular item. It requires the list to be in sorted order, and uses that fact to find an element quickly.

It's important to note, however that each step doesn't cut it exactly in half. If the array is of even length, and there is no 'middle', we have to take either a smaller or a larger portion. But this is a good intuitive approach.

Example 5: Merge Sort

Let's introduce one other idea here: arbitrary units of time. While the exact time something will take will depend on the machine, on the particular operations, etc., we can get a general sense of time through our arbitrary units (AU).

Now that we have selection sort, let's talk about merging.

Say we have two sorted arrays that we want to combine into a single big sorted array. We could append one to the other, and then re-sort it, but that doesn't make use of the fact that each individual array is already sorted. How can we use this to our advantage?

It turns out, we can merge them more quickly using the sorted property. The smallest element must be at the start of one of the two lists. So let's compare those, and put the smallest element at the start of our new list.

Recurrence relations

Summary

• There are no magic shortcuts for analyzing code runtime.
• In our course, it’s OK to do exact counting or intuitive analysis.
• Know how to sum 1 + 2 + 3 + ... + N and 1 + 2 + 4 + ... + N.
• We won’t be writing mathematical proofs in this class.
• Many runtime problems you’ll do in this class resemble one of the five problems from today. See textbook, study guide, and discussion for more practice.
• This topic has one of the highest skill ceilings of all topics in the course. All the tools are here, but practice is your friend!
• Different solutions to the same problem, e.g. sorting, may have different runtimes (with big enough differences for the runtime to go from impractical to practical!).

disc08: More Asymptotic Analysis

The meta-strat on this problem is to explore a rigourous framework to analyze running time for recursive procedures. Specifically, one can derive the running time by drawing the recursive tree and accounting for three pieces of information.

• The height of the tree.
• The branching factor of each node.
• The amount of work each node contributes relative to its input size.

Give the running time in terms of N.

1

public void andslam(int N) {
    if (N > 0) {
        for (int i = 0; i < N; i += 1) {
            System.out.println("datboi.jpg");
        }
        andslam(N / 2);
    }
}

1. Height of tree
   How many time can you divided n by 2 until you get n = 1.
   Let h be height, n/2^h = 1 => n = 2^h => h = log(n)

2. Branching factor
   Note each time addslam is called, it makes 1 recursive called on n/2.
   -> nodes per layer = 1

3. Amout of work each node does
   -> linear recursive to input size, so O(n)

Running time of entire recursive procedure can be calculate by summing over entire recursive tree.

running time = (sum over layers) * (nodes/layer) * (amoun work/1 node)