# 15-112: Fundamentals of Programming and Computer Science Class Notes: Efficiency

Use the following notes, except:
• Add these topics:

• Input Size
• For list L: n = # of elements in the list == len(L)
• For integer n: we generally use n in 112, but technically should use size(n) == # of bits to represent n = log2(n)

• Sorting Links

• BubbleSort
You are responsible for writing (from scratch), understanding, and analyzing SelectionSort, BubbleSort, and MergeSort, and any reasonable variations of those. See here.

• Sort Properties
• Time Complexity (best, average, and worst cases). Note: in 112, we mostly prove best and worst cases.
• Space Complexity (best, average, and worse cases).
• In-Place (Uses O(1) space; ie, constant-sized memory (not counting the input))
• Stable (maintains relative order of equal values)
• Adaptive (recognizes pre-sorted lists)
• Comparison-Based. Note: best-possible comparison-based algorithm is O(nlogn)
• Serial or Parallel. Note: we only consider serial sorts in 112.
• Implementation Details
• Iterative vs Recursive
• Destructive vs Nondestructive

• Omit these topics:
• Omit example #4 (isPrime(nthHappyNumber(n)))
• Omit example #6 (Sum of Prime Factors)