1 Warmup Runtime Questions
1.1 Informal
What is the runtime of:
1. Searching for a element in an unordered list?
2. BFS
3. Checking if a number is even or odd?
4. Travelling Salesman?
5. Searching for element in balanced binary search tree?
2 Formal
Formal definition of Big Oh: ∃c,n0 : ∀n > n0 : f(n) ≤ cg(n) 1. Prove that f(n) = O(n2), given
f(n) = O(n + g(n))
g(n) = O(n2)
2. Prove that f(n) = O(n3), given f(n) = O(n∗g(n)) g(n) = O(n2)
3. Prove that f(n) = O(logn), given
f(n) = O(log(g(n)))
g(n) =
2 3
n + 20c
1
3 Sorting Algorithms
Sorting algorithms are given an unsorted list of elements and output a list with the same elements, now sorted by some key. We can assume that the input is a list of unique integers without loss of generality. Online algorithm visualizers can be helpful to remind yourself how they work.
3.1 InsertionSort
1 def InsertionSort(lst): 2 \\ 1st loop 3 for (i in range(1,len(lst)-1)): 4 j = i – 1 5 \\ 2nd loop 6 while (j > 0 and lst[j]<lst[i]: 7 j-=1 8 lst.insert(j, lst.pop(i)) 9 return lst
How can we analyze the runtime? Try to find the worse case: Reverse sorted. Ex: 8,7,6,5,4,3,2,1 Draw a n∗n grid to show the maximum number of operations. For each element in the outer loop, i, it is potentially compared to every element before it, j. The first i only is compared once so fill in 1 box in the first row of the grid (from the left). Next, the second i can be compared twice, so fill in 2 boxes. Continue to show how the number of operations can be represented by a triangle in the grid (looks like lower triangular matrix).
1 + 2 + 3 + 4 + … + n−1 + n =
n(n + 1) 2
= O(n2)
