COMPSCI 61B Lecture Notes - Lecture 18: Webcast, Merge Sort, Amortized Analysis
1 Jun 2017
School
Department
Course
Professor
Document Summary
Project 2 extra credit autograder due 3/2 at 11:59 pm. Lecture today/friday introduce only small amount of new content (due to p2) See study guides for each lecture starting monday: Webcast viewers, do all b-level problems in guide after lecture/before next lecture. To understand how code scales, we symbolically count number of executions of a representative operation as a function of input size n. Focus on behavior for large n: ignore lower order terms. Find a simple f(n) such that the runtime r(n) is an element of theta(f(n)) in the worst case. Worst case number of j += 1 calls: 1 + 2 + 3 + + (n - 2) + (n - 1) Cs 70 and especially cs 170 will cover this in much more detail. Not a math class, though we"re expected to know these two: Every time we increase n by 1, we double the work! Another approach: count number of class to f3, given by c(n)
