Recurrences
Methods for solving recurrences
 Substitution: Guess and check
 Recursion tree: Draw a tree, sum computation at nodes; very general
 Master Theorem: Formula for large class of recurrences
Master Theorem
 Video
 How work at root compares to work at leaves (i.e. number of leaves, since base case has input of size 1)
 $l = \log_b n$ levels, $a^l = a^{\log_b n} = n^{\log_b a}$ leaves
 Case 1: leaves dominate; so much work at the bottom that the other levels don't matter; number of leaves grows polynomially faster with $n$ than work at the root does
 Case 2: log/polylog factor worse
 Case 3: root work $f(n)$ grows polynomially faster, is lower bounded by the leaves' growth, so $\Theta(f(n))$
 If $f(n)$ is polynomial s.t. $f(n) = \Theta(n^c)$ for $c \geq 0$, then the cases are simplified
 Q: If the master theorem is about trees — comparing work at root vs at leaves — why are recursion trees more general? What restrictions do the assumptions of the master theorem add?
 "Work done" is number of operations we need to do
Exercises
 Use (strong) induction for verifying substitution guess. Base case is usually trivial: $T(1) = O(h(1)) = O(1)$. Assume true for all $n' > n$, then show for $n$. By assumption, $T(n) \leq a \left[ c \cdot h(g(n)) \right] + f(n)$. Show that that $\leq c \cdot h(n)$.
 Some recursion trees are chains, i.e. if branching factor is 1
 To find number of levels: $\frac{n}{(3/2)^l} = 1$
 Omg most people said "2" re: binary search recurrence coefficient and I said "1" so I thought I was wrong BUT I WAS RIGHT
Sequence Interface
 Collection of items in extrinsic order; each item has a rank because some external party put it there
 Generalization of stacks and queues, which support a subset of sequence operations

Operations
 Container:
build(X)
, len()
 Static:
iter_seq()
, get_at(i)
, set_at(i, x)
 Dynamic:
insert_at(i, x)
, delete_at(i)
, insert_first/last(x)
, delete_first/last()
 We'll discuss three data structures to implement the sequence inteface: arrays, linked lists, dynamic arrays
Set Interface
 Collection of items based on intrinsic property, usually a unique key
 Generalizations of dictionaries and other intrinsic query databases

Operations
 Container:
build(X)
, len()
 Static:
find(k)
 Dynamic:
insert(x)
, delete(k)
 Order:
iter_ord()
, find_min()
, find_max()
, find_next(k)
, find_prev(k)
Sequence Implementations
Three data structures
Array Sequence
 Many processes may share the same main memory store, so OS assigns a fixed chunk of memory addresses to each active process
 Amount of memory allocated depends on needs of process and availability of free memory
 If we store an array A, then B right next to it, then want to add to A, better to request a new range of memory, copy A, add the new item to the end, and free up A's original space
get_at
and set_at
are $O(1)$ because of our random access machine
 Deleting or inserting involve moving items and resizing array, so lineartime in worst case
Linked List Sequence
 Pointerbased or linked
 Stores address of head (node storing first element of list), linked list's size, and number of items in linked list
 Stores each item in a node, a constantsized container with two properties:
node.item
storing the item, node.next
storing the memory address of the node containing the next item in the sequence
 Adding new item at head takes $O(1)$ time to relink pointers
get_at
and set_at
worstcase linear time to step through items onebyone
Dynamic Array Sequence
See rec 3