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

  • DECATUR JUST DESTROYED PHILADELPHIA Decatur promoted to Captain

    DECATUR JUST DESTROYED PHILADELPHIA Decatur promoted to Captain

    harbour. at any of the islands she always had him brought over. Son A. Legitimate. Land based. Marriage to daughter of land wealthy land dweller. Given a house in the city of Macau. ... Congressman Ron Paul . Presented Congress...
  • Maths Games - doubleme.org

    Maths Games - doubleme.org

    CountDown. Take three single digit cards to make a three digit target number. Write down the number and replace the cards (take the 0 card out now).
  • Onko - Pavol Jozef Šafárik University

    Onko - Pavol Jozef Šafárik University

    (zlá otázka) Veľký počet mutácií v rôznych bunkách, ale 99 % sa neuplatní Mutácia, ktorá umožní rýchlejšie delenie, dá vznik rakovinovému subklónu a po každom kroku je to horšie (dediferenciácia, instabilita genómu) TEÓRIA KLÓNOVEJ SELEKCIE CELULÁRNY DARWINIZMUS Vírusové onkogény (v-onc)...
  • Funding Opportunities - University of Vermont

    Funding Opportunities - University of Vermont

    Objective of CDI: Enhance American competitiveness by enabling innovation through the use of computational thinking CDI is unique within NSF five-year initiative; minimum of $26M in FY 2008 to create revolutionary science and engineering research outcomes made possible by innovations...
  • Tasks, design and the architecture of pedagogic spaces

    Tasks, design and the architecture of pedagogic spaces

    Advice to novice architects, (Potter, 2002) Enter old buildings alertly, on the prowl for trouble. Note any evidence of smell, subsidence, cracking, rot, woodworm, damp, loose plaster, stuck doors, pattern staining, damaged fittings. Always note the superficial nature and conditions...
  • Prefixes and Suffixes

    Prefixes and Suffixes

    Mrs. Chantz Tigers English 2007-2008 Table of Contents Goals Standards Lesson Assessment Games Goals By the end of this PowerPoint, I want you to be able to: Recall the meaning of several common prefixes Understand how prefixes change word meanings...
  • Languages and Finite Automata - Computer Science

    Languages and Finite Automata - Computer Science

    Times New Roman Comic Sans MS class Microsoft Equation 3.0 Context-Free Languages Slide 2 Slide 3 Context-Free Grammars Grammars Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Another Example Slide 12 Slide 13 Slide 14 Slide 15 A...
  • Practical application of Inuit principles, ethics and ...

    Practical application of Inuit principles, ethics and ...

    25% live outside the Nunangat- growing numbers of urban Inuit living in Ottawa, Edmonton, Winnipeg, Montreal and St. John's. Diversity among Inuit Income/employment diversity: 61% of working age Inuit are employed, some in government or mining/resource extraction industries in the...