Week 1 Searching for a element in an unordered list

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:
9c; n0 : 8n 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(log n), given
f(n) = O(log(g(n)))
g(n) = 2
3
n + 20c
13 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)