Welcome! Take one of the packets stacked near the door.

Welcome! Take one of the packets stacked near the door.

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))

Recently Viewed Presentations

  • Vasco da Gama - MrDonn.org

    Vasco da Gama - MrDonn.org

    Vasco da Gama was the third son of a noble family in Portugal. He was born around 1460. He was the first European to reach India by sea. His sea career began when he was old enough to join the...
  • The Challenge: To Create More Value in All Negotiations

    The Challenge: To Create More Value in All Negotiations

    "They" hate it if you call them "bankers." "They" love it, on the other hand, when you ask to see their #s—stupendous. "They" are … Commerce Bank. These absurdly fast growing, insanely profitable "retailers," rewriting the rules of East Coast...
  • parents ministry & reward parent as an encourager

    parents ministry & reward parent as an encourager

    Be a PRAYER WARRIOR! What a comfort to know* that God hears the prayers of the righteous (Prov. 15:29). Prayer brings us the encouragement, strength, and wisdom we need to fulfill our role as biblical parents. Remember, our intent in...
  • Quick Review in Chemistry

    Quick Review in Chemistry

    Cayley's Enumeration on the Structural Isomers of Alkanes Matthew P. Yeager Also: topoisomers, isotopomers, nuclear isomers, spin isomers Significance of Isomers Isomers contain identical molecular formulas, but differ in structural formulas, thereby generating various compounds of different physical properties Important...
  • P2P Conference - Trip Report - Stanford University

    P2P Conference - Trip Report - Stanford University

    P2P Conference - Trip Report Ilya Mironov, Crypto group The conference The O'Reilly Peer-to-Peer conference Feb. 14-16, 2001, San Francisco "The first and most important conference on P2P" About 900 attendees, 75 speakers.
  • Searching for Optical Transient Counterparts of GW triggers ...

    Searching for Optical Transient Counterparts of GW triggers ...

    Searching for Electromagnetic Counterparts of Gravitational-Wave Transients. MaricaBranchesi(UniversitàdiUrbino/INFN) on . behalf of . LIGO . Scientific Collaboration . and. Virgo. Collaboration & Alain . Klotz (TAROT . telescope) Myrtille. Laas-Bourez (Zadko. telescope) DCC: G1100079
  • Meter removal and installation certification

    Meter removal and installation certification

    We Energies has policies prohibiting electricians from cutting meter seals and removing meters when performing residential service rewires. These policies were created to keep electricians and homeowners safe. In certain scenarios, a certifiedlicensed electriciancan disconnect a service and remove and...
  • Pride &amp; Prejudice - edl

    Pride & Prejudice - edl

    Pride & Prejudice Volume One Objective: Students will use their knowledge of critically evaluate the novel, Pride and Prejudice, by using the Comedic Ladder in order to help them identify the correct type of aesthetic quality