recurrence relations

Question 1

insertion sort algorithm

Answer 1

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Question 2

insertion sort time complexity

Answer 2

O(n^2)

Question 3

merge sort running time

Answer 3

worst case time complexity O(n log n)

Question 4

merge sort algorithm

Answer 4

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Question 5

Substitution method advantages and disadvantages

Answer 5

Guess a solution and check if it is correct
Pros: rigorous, formal solution
Cons: requires induction, how do you guess?

Question 6

Recursion trees advantages and disadvantages

Answer 6

Build a tree representing all recursive calls, infer the solution
Pros: intuitive, visual, can be used to guess
Cons: not too formal

Question 7

Master method advantages and disadvantages

Answer 7

Check the cookbook and apply the appropriate case
Pros: formal, useful for most recurrences
Cons: have to memorize, useful for most recurrence

Question 8

substitution method steps

Answer 8

Steps
*Guess the solution
*Use induction to show that the solution works

What is induction?
A method to prove that a given statement is true for all-natural numbers 𝑘
Two steps
Base case: show that the statement is true for the smallest value of 𝑛 (typically 0)
Induction step: assuming that the statement is true for any 𝑘, show that it must also hold for 𝑘+1

Question 9

master method recurrence function template

Answer 9

𝑇(𝑛)=𝑎𝑇(𝑛/𝑏)+𝑓(𝑛)
Compare 𝑛^log_𝑏⁡𝑎 vs. 𝑓(𝑛)

Question 10

master method case 1

Answer 10

if f(n) < n^log_b(a)
then theta(n^log_b(a))

Question 11

master method case 2

Answer 11

if f(n) = n^log_b(a)
then theta( n^log_b(a) * log(n))

Question 12

master method case 3

Answer 12

if f(n) > n^log_b(a)
then theta(f(n))
and a.f(n/b) ≤ k.f(n)

Question 13

master method, all three cases

Answer 13

Intuition: the larger of the two functions determines the solution

The three cases compare 𝑓(𝑛) with 𝑛^log_𝑏⁡(𝑎)
Case 1: 𝑛^log_𝑏⁡(𝑎) is larger – 𝑂 definition
Case 2: 𝑓(𝑛) and 𝑛^log_𝑏⁡(𝑎) grow at the same rate – Θ definition
Case 3: 𝑓(𝑛) is larger – Ω definition

Question 14

columns in recurrence tree method

Answer 14

recursive call
#nodes
tree
row sum