This is the lecture note of CS61B - Lecture 15.
In this lecture, we will try to do some exercises to make us understand asymptotic analysis more deeply.
Example 1 and 2: For Loop
The Answer is C.
Runtime analysis often requires careful thought. CS70 and especially CS170 will cover this in much more detail.
Example 3: Recursion
The answer is E. This answer is from intuition. How to get the answer from math?
The answer is D.
Example 4: Binary Search
This is also an example of recursion.
The answer is B, since problem size halves over and over until it gets down to 1.
How to do exact counting?
Example 5: Merge Sort
The last example we will see is Merge Sort.
First, what is merging?
Given two sorted arrays, the merge operation combines them into a single sorted array by successively copying the smallest item from the two arrays into a target array.
The answer is C.
We can optimize selection sort by using merge operation. And the idea behind the process is called "Divide and Conquer".
There is an interesting question: for an array of size N, what is the worst case runtime of Mergesort?
Nlog N is basically as good as N, and is vastly better than N^2