CSE 373: Data Structures and Algorithms Lecture 4: Asymptotic Analysis part 3 Code Style, Recurrence Relations, Formal Big-O & Cousins Instructor: Lilian de Greef Quarter: Summer 2017 Code Style Why does code style matter? Code Style Do

Dont Code Style Critique Code Style Critique #2 Code Style Critique #3 Code Style Critique #4

Recurrence Relations How to calculate Big-O for recursive functions! (Continued from last lecture) Example #1: Towers of Hanoi // Prints instructions for moving disks from one // pole to another, where the three poles are // labeled with integers "from", "to", and "other". // Code from rosettacode.org public void move(int n, int from, int to, int other) { if (n == 1) {

System.out.println("Move disk from pole " + from + " to pole " + to);} else { move(n - 1, from, other, to); move(1, from, to, other); move(n - 1, other, to, from); } } Example #1: Towers of Hanoi if (n == 1) {

System.out.println("Move disk from pole " + from + " to pole " + to);} else { move(n - 1, from, other, to); move(1, from, to, other); move(n - 1, other, to, from); } Base Case: Recurrence Relation:

(Example #1 continued) (Example #1 continued) Example #2: Binary Search 2 3 5

16 37 50 73 75

126 Find an integer in a sorted array (Can also be done non-recursively) // Requires the array to be sorted. // Returns whether k is in array. public boolean find(int[]arr, int k){ return help(arr,k,0,arr.length); } private boolean help(int[]arr, int k, int lo, int hi) {

int mid = (hi+lo)/2; // i.e., lo+(hi-lo)/2 if(lo==hi) return false; if(arr[mid]==k) return true; if(arr[mid]< k) return help(arr,k,mid+1,hi); else return help(arr,k,lo,mid); What is the recurrence relation? // Requires the array to be sorted. // Returns whether k is in array.

public boolean find(int[]arr, int k){ return help(arr,k,0,arr.length); } private boolean help(int[]arr, int k, int lo, int hi) { int mid = (hi+lo)/2; // i.e., lo+(hi-lo)/2 if(lo==hi) return false; if(arr[mid]==k) return true; if(arr[mid]< k) return help(arr,k,mid+1,hi); else

return help(arr,k,lo,mid); A. 2T(n-1) + 3 C. T(n/2) + 3 B. T(n-1)*T(n-1) + 3 D. T(n/2) * T(n/2) + 3 Base Case:

Recurrence Relation: (Example #2 continued) (Example #2 continued) Recap: Solving Recurrence Relations 1. Determine the recurrence relation. What is the base case? T(n) = 3 + T(n/2) T(1) = 3

2. Expand the original relation to find an equivalent general expression in terms of the number of expansions. T(n) = 3 + 3 + T(n/4) = 3 + 3 + 3 + T(n/8) = = 3k + T(n/(2k)) 3. Find a closed-form expression by setting the number of expansions to a value which

reduces the problem to a base case n/(2k) = 1 means n = 2k means k = log2 n So T(n) = 10 log2 n + 8 (get to base case and do it) So T(n) is O(log n) Common Recurrence Relations Should know how to solve recurrences but helps to recognize some

common ones: T(n) = O(1) + T(n-1)linear T(n) = O(1) + 2T(n/2) linear T(n) = O(1) + T(n/2) logarithmic O(log n) T(n) = O(1) + 2T(n-1) exponential T(n) = O(n) + T(n-1) quadratic T(n) = O(n) + T(n/2)

linear (why?) T(n) = O(n) + 2T(n/2) O(n log n) Big-O Big Picture with its formal definition In terms of Big-O, which function has the faster asymptotic running time? worst-case running time

f(n) g(n) 0 1 2 3

4 5 6 7 8

n In terms of Big-O, which function has the faster asymptotic running time? worst-case running time g(n) f(n) 0

100 200 300 400 500 600 700 800 n In terms of Big-O, which function has the faster asymptotic running time? worst-case running time f(n) g(n)

0 500 1000 Take-away: 1500 2000

2500 3000 3500 4000 n Formal Definition of Big-O

General Idea explanation from last week: Mathematical upper bound describing the behavior of how long a function takes to run in terms of N. (The shape as N ) Formal definition of Big-O: Formal Definition of Big-O Using the Formal Definition of Big-O Definition: f(n) is in O( g(n) ) if there exist constants c and n0 such that f(n) c g(n) for all n n0

To show f(n) is in O( g(n) ), pick a c large enough to cover the constant factors and n0 large enough to cover the lower-order terms Example: Let f(n) = 3n2+18 and g(n) = n2 Example: Let f(n) = 3n2+18 and g(n) = n5 Practice with the Definition of Big-O Let f(n) = 1000n and g(n) = n2

What are some values of c and n0 we can use to show f(n)O(g(n))? O(g(n))? Definition: f(n) is in O( g(n) ) if there exist constants c and n0 such that f(n) c g(n) for all n n0 More Practice with the Definition of Big-O Let a(n) = 10n+3n2 and b(n) = n2 What are some values of c and n0 we can use to show a(n)O(g(n))? O(b(n))?

Definition: f(n) is in O( g(n) ) if there exist constants c and n0 such that f(n) c g(n) for all n n0 Constants and Lower Order Terms The constant multiplier c is what allows functions that differ only in their largest coefficient to have the same asymptotic complexity Example: Eliminate lower-order terms because Eliminate coefficients because

3n2 vs 5n2 is meaningless without the cost of constant-time operations Can always re-scale anyways Do not ignore constants that are not multipliers! n3 is not O(n2), 3n is not O(2n) Cousins of Big-O Big-O, Big-Omega, Big-Theta, little-o, little-omega Big-O & Big-Omega Big-O: Big-:

f(n) is in O( g(n) ) if there exist constants c and n0 such that f(n) c g(n) for all n n0 f(n) is in ( g(n) ) if there exist constants c and n0 such that f(n) c g(n) for all n n0

Big-Theta Big- : f(n) is in ( g(n) ) if f(n) is in both O(g(n)) and (g(n)) little-o & little-omega little-o: little-: f(n) is in o( g(n) ) if

constants c >0 there exists an n0 s.t. f(n) c g(n) for all n n0 f(n) is in ( g(n) ) if constants c >0 there exists an n0 s.t. f(n) c g(n) for all n n0 Big-O, Big-Omega, Big-Theta Which one is more useful to describe asymptotic behavior?

A common error is to say O( f(n) ) when you mean ( f(n) ) A linear algorithm is in both O(n) and O(n5) Better to say it is (n) That means that it is not, for example O(log n) Notes on Worst-Case Analysis Analyzing Worst-Case Cheat Sheet Basic operations take some amount of constant time

Arithmetic (fixed-width) Assignment Access one Java field or array index etc. (This is an approximation of reality: a very useful lie)

Control Flow Consecutive statements Conditionals Loops Method calls Recursion Time Required Sum of time of statement Time of test plus slower branch

Sum of iterations * time of body Time of calls body Solve recurrence relation Comments on Asymptotic Analysis Is choosing the lowest Big-O or Big-Theta the best way to choose the fastest algorithm? Big-O can use other variables (e.g. can sum all of the elements of an n-by-m matrix in O(nm))