Computer Science 15-112, Fall 2012
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))
   5. Sum of squares example

      # The following functions all solve the same problem:
      # Given a non-negative integer n, return True if n is the sum
      # of the squares of two non-negative integers, and False otherwise.
      
      def f1(n):
          for x in xrange(n+1):
              for y in xrange(n+1):
                  if (x**2 + y**2 == n):
                      return True
          return False
      
      def f2(n):
          for x in xrange(n+1):
              for y in xrange(x,n+1):
                  if (x**2 + y**2 == n):
                      return True
          return False
      
      def f3(n):
          xmax = int(n**0.5)
          for x in xrange(xmax+1):
              for y in xrange(x,n+1):
                  if (x**2 + y**2 == n):
                      return True
          return False
      
      def f4(n):
          xyMax = int(n**0.5)
          for x in xrange(xyMax+1):
              for y in xrange(x,xyMax+1):
                  if (x**2 + y**2 == n):
                      return True
          return False
      
      def f5(n):
          xyMax = int(n**0.5)
          for x in xrange(xyMax+1):
              y = int((n - x**2)**0.5)
              if (x**2 + y**2 == n):
                  return True
          return False
      
      def testFunctionsMatch():
          # first, verify that all 5 functions work the same
          maxToCheck = 200
          print "Verifying that all functions work the same..."
          for n in xrange(maxToCheck):
              assert(f1(n) == f2(n) == f3(n) == f4(n) == f5(n))
          print "All functions match up to n =", maxToCheck
      
      testFunctionsMatch()
      
      import time
      def timeFnCall(f, n):
          # call f(n) and return time in ms
          # Actually, since one call may require less than 1 ms,
          # we'll keep calling until we get at least 1 secs,
          # then divide by # of calls we had to make
          calls = 0
          start = end = time.time()
          while (end - start < 1):
              f(n)
              calls += 1
              end = time.time()
          return float(end - start)/calls*1000 #(convert to ms)
      
      def timeFnCalls(n):
          print "\n***************"
          for f in [f1, f2, f3, f4, f5]:
              print ("%s(%d) takes %8.3f milliseconds" %
                     (f.__name__, n, timeFnCall(f, n)))
      
      timeFnCalls(1001)
      timeFnCalls(2002)

   6. Sum of Prime Factors example

      # The following functions all solve the same problem:
      # Given a non-negative integer n, return the sum of its
      # prime factors (with repetition, so f(4) = 2+2, since 4 == 2**2).
      
      def isPrime(n):
          if (n < 2):
              return False
          if (n == 2):
              return True
          if (n % 2 == 0):
              return False
          maxFactor = int(round(n**0.5))
          for factor in xrange(2,maxFactor+1):
              if (n % factor == 0):
                  return False
          return True
      
      def nthPrime(n):
          found = 0
          guess = 0
          while (found <= n):
              guess += 1
              if (isPrime(guess)):
                  found += 1
          return guess
      
      def powerOfPrimeFactor(n, primeFactor):
          power = 0
          while (n % (primeFactor**(power+1)) == 0):
              power += 1
          return power
      
      def f1(n):
          sum = 0
          k = 0
          while (nthPrime(k) <= n):
              if (n % nthPrime(k) == 0):
                  # found a prime factor
                  sum += nthPrime(k) * powerOfPrimeFactor(n, nthPrime(k))
              k += 1
          return sum
      
      def f2(n):
          sum = 0
          k = 0
          prime = nthPrime(k)
          while (prime <= n):
              if (n % prime == 0):
                  # found a prime factor
                  sum += prime * powerOfPrimeFactor(n, prime)
              k += 1
              prime = nthPrime(k)
          return sum
      
      def f3(n):
          sum = 0
          for prime in xrange(2, n+1):
              if (isPrime(prime) and (n % prime == 0)):
                  # found a prime factor
                  sum += prime * powerOfPrimeFactor(n, prime)
          return sum
      
      def f4(n):
          sum = 0
          for prime in xrange(2, n+1):
              if ((n % prime == 0) and isPrime(prime)):
                  # found a prime factor
                  sum += prime * powerOfPrimeFactor(n, prime)
          return sum
      
      def f5(n):
          sum = 0
          for prime in xrange(2, n+1):
              if (n % prime == 0):
                  # found a prime factor
                  power = powerOfPrimeFactor(n, prime)
                  sum += prime * power
                  n /= (prime ** power)
                  if (n <= 1): break
          return sum
      
      def f6(n):
          # Same as f5(n), with powerOfPrimeFactor inlined
          sum = 0
          for prime in xrange(2, n+1):
              if (n % prime == 0):
                  # found a prime factor
                  power = 0
                  while (n % (prime**(power+1)) == 0):
                      power += 1
                  sum += prime * power
                  n /= (prime ** power)
                  if (n <= 1): break
          return sum
      
      def f7(n):
          sum = 0
          for prime in xrange(2, n+1):
              while (n % prime == 0):
                  sum += prime
                  n /= prime
              if (n <= 1): break
          return sum
      
      def f8(n):
          sum = 0
          primeProduct = 1
          for prime in xrange(2, n+1):
              while (n % (primeProduct*prime) == 0):
                  sum += prime
                  primeProduct *= prime
              if (primeProduct == n): break
          return sum
      
      def f9(n):
          sum = 0
          primeProduct = 1
          for prime in xrange(2, n+1):
              while (n % (primeProduct*prime) == 0):
                  sum += prime
                  primeProduct *= prime
                  if (primeProduct == n): break
          return sum
      
      def testFunctionsMatch():
          # first, verify that all 5 functions work the same
          maxToCheck = 200
          print "Verifying that all functions work the same..."
          for n in xrange(maxToCheck):
              target = f1(n)
              for f in [f2, f3, f4, f5, f6, f7, f8, f9]:
                  assert(f(n) == target)
          print "All functions match up to n =", maxToCheck
      
      testFunctionsMatch()
      
      import time
      def timeFnCall(f, n):
          # call f(n) and return time in ms
          # Actually, since one call may require less than 1 ms,
          # we'll keep calling until we get at least 1 secs,
          # then divide by # of calls we had to make
          calls = 0
          start = end = time.time()
          while (end - start < 1):
              f(n)
              calls += 1
              end = time.time()
          return float(end - start)/calls*1000 #(convert to ms)
      
      def timeFnCalls(n, useReverse=False):
          print "\n***************"
          fns = [f1, f2, f3, f4, f5, f6, f7, f8, f9]
          if (useReverse): fns = reversed(fns)
          for f in fns:
              print ("%s(%d) takes %8.3f milliseconds" %
                     (f.__name__, n, timeFnCall(f, n)))
      
      timeFnCalls(792) # 2**3 * 3**2 * 11**1
      timeFnCalls(32472, True) # 2**3 * 3**2 * 11**1 * 41**1

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