Computer Science 15-112, Fall 2011
Class Notes:  Efficiency

1. Required Reading
2. Big-Oh
3. Common Function Families
4. Efficiency
5. The Big Idea
6. Examples

Efficiency

1. Required Reading
   1. Wikipedia page on Big-Oh Notation (you may gloss over the formal details!)
       
2. Big-Oh
   1. Describes asymptotic behavior of a function
   2. Informally (for 15112):  ignore all lower-order terms and constants
   3. Formally (after 15112):  see here
   4. A few examples:
   • 3n² - 2n + 25 is O(n²)
   • -30000n² + 2n - 25 is O(n²)
   • 0.00000000001n² + 123456789n is O(n²)
   • 10nlog₁₇n + 25n - 17 is O(nlogn)
      
3. Common Function Families
   1. Common Function Families (in increasing size)
      1. Constant  (k)
      2. Logarithmic  (log_kn)
      3. Square-Root (n^0.5)
      4. Linear  (kn)
      5. Linearithmic, Loglinear, or quasilinear  (nlogn)
      6. Quadratic  (kn²)
      7. Exponential  (kⁿ)
   2. Graphically
      (Images borrowed from here)
      
      
      
      
      
       
4. Efficiency
   • When we say the program runs in O(f(n)), we mean...
     • n is the size of our input
     • f(n) = resource consumption of our program
       • time, space, bandwidth, ...
       • For 15112, we mainly care about time
   • For time, we usually measure algorithmic steps rather than elapsed time
     (These share the same big-oh, but algorithmic steps are easier to precisely describe and reason over)
     • Count steps in a written algorithm, or comparisons and swaps in a list, etc
     • Can time your code's execution with:  time.time()
        
5. The Big Idea
   • Each function family grows much faster than the one before it!
   • And: on modern computers, any function family is usually efficient enough on small n, so we only care about large n
   • So...  Constants do not matter nearly as much as function families
   • Practically...
     • Do not prematurely or overly optimize your code
     • Instead:  think algorithmically
        
6. Examples
   1. isPrime versus fasterIsPrime
   2. linear search versus binary search
      • Definitions
        • Linear search:  check each element in turn
        • Binary search:  check middle element, eliminate half on each pass
      • Number-guessing game
      • Find a value in a sorted list (if we knew about lists...)
      • Find a root (zero) of a function with bisection (really just binary search)
   3. selectionsort versus mergesort
      • See David Eck's most-excellent xSortLab
      • Also see these fun dancing-based visualizations of selectionsort and mergesort
      • Definitions
        • selectionsort: repeatedly select largest remaining element and swap it into sorted position
        • mergesort:  sort blocks of 1's into 2's, 2's into 4's, etc, on each pass merging sorted blocks into sorted larger blocks
      • Analysis (in class)
   4. From lab2:  isPrime(nthHappyNumber(n))

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem