Recurrence Relations

Question 1

QuickSort

Answer 1

QS(n) = QS(s-left) + QS(right - s) + O(n), n = right - left

Question 2

partitioning around a pivot

Answer 2

O(nlogn)

Question 3

QuickSort best case

Answer 3

theta (nlogn)

Question 4

QuickSort worst case

Answer 4

theta (n^2)

Question 5

QuickSort average case

Answer 5

theta (nlogn)

Question 6

QuickSelect average case

Answer 6

C(n) = C(n/2) + (n+1)
theta (n)

Question 7

QuickSelect worst case

Answer 7

theta (n^2)

Question 8

Closest Pairs
sorting: O(nlogn)
splitting: T(n/2)

Answer 8

T(n) = 2T(n/2) + O(nlogn)
T(n) = O(n (logn)^2 )

Question 9

BFS running time

Answer 9

O(n)
or O(edges + nodes)

Question 10

DFS running time

Answer 10

O(n) or O(edges + nodes)

Question 11

Topological Sort

Answer 11

O (n)
O (m+n)

Question 12

Heap operations

Answer 12

Insert: O (log n)
extract min: O (log n)
find min: O (1)
heapify O(n)
delete: O( log n )

Question 13

Heapsort

Answer 13

O(nlogn)

Question 14

Dijkstra’s

Answer 14

O (edge + vertices*log (vertices) )
runtime: 0 (#edges * #vertices)

Question 15

max weight independent set

Answer 15

maxVal(i) = max {maxVal(i - 1), maxVal(i-2) + Ci}
for gap of 2: max {maxVal(i - 1), maxVal(i - 2), maxVal(i - 3) + Ci}

Question 16

weighted path

Answer 16

totCost(i, j) = max {totCost (i - 1, j), totCost (i, j - 1)} + Cij

Question 17

knapsack

Answer 17

V (n, w) = max { V ( n-1, w ), V ( n - 1, W - Wn ) + Vn }

Question 18

long increasing subsequence in 1d array

Answer 18

F (k) = max (i < k) and (xi < xk) { F (i) } + 1

Question 19

longest common subsequence

Answer 19

if s1i = s2i: LCS ( i, j ) = LCS ( i - 1, j - 1 ) + 1
if s1i NOT = s2i: LCS ( i, j ) = max { LCS ( i - 1, j ) , LCS ( i, j - 1) }

Question 20

optimal binary search tree

Answer 20

C [i, j] = min {C [i, k + 1], C [k + 1, j]} + sum of probabilities up to j (pic in text chain)