Quiz 2 - Recursion, Recurrence Relations and Divide & Conquer

Question 1

Which of the following correctly defines what a ‘recurrence relation’ is?

• An equation (or inequality) that represents nth iteration of a sequence in terms of n. That includes an initial condition.
• T(n)=T(n-1)+2n, T(0)=1
• An equation (or inequality) that relates the nth element of a sequence to its predecessors (recursive case). This includes an initial condition (base case).
• T(n) = 2(1+n), T(0) = 2

Answer 1

An equation (or inequality) that relates the nth element of a sequence to its predecessors (recursive case). This includes an initial condition (base case).

Question 2

Given the following algorithm

foo(n)
if n <= 1
return 1
else
x = foo(n-1)
for i = 1 to n
x = x + i
return x
Determine the asymptotic running time. Assume that addition can be done in constant time.

Answer 2

Theta(n^2)

Question 3

What is the solution of
T(n) = 2T(n/2) + n^2
using the Master theorem?

Answer 3

Theta(n^2), case 3

Question 4

Solve the following recurrence by giving the tightest bound possible.

T(n) = 4T(n/4) + 4n

Answer 4

Theta(nlogn)

Question 5

What is the solution of
T(n) = 2T(n/2) + n/logn
using the Master theorem?

Answer 5

Master Method does not apply.

Question 6

We can use Divide and Conquer technique to solve a problem in which of the following scenarios?

• The complexity is exponential to solve the entire problem
• None of the options
• The subproblems are overlapping so we don’t have to solve them over and over again
• We can break the problem into several subproblems that are similar to the original problems but smaller in size

Answer 6

• We can break the problem into several subproblems that are similar to the original problems but smaller in size

Question 7

What would be the time complexity of the following algorithm?

int sum = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
if (i == j == k) {
for (l = 0; l < nnn; l++) {
sum = i + j + k + l;
}
}
}
}
}

Answer 7

Theta(n^4)

Question 8

What would be the time complexity of the following algorithm?

reverse(a):
for i = 1 to len(a)-1
x = a[i]
for j = i downto 1
a[j] = a[j-1]
a[0] = x

Answer 8

O(n^2)

Question 9

Which of the following equations correctly represent the factorial function.
* f(n) = n f(n-1)
* f(n) = n f(n)
* f(n-1) = n f(n)
* f(n) = (n-1) f(n-1

Answer 9

• f(n) = n f(n-1)

Question 10

Which of the following recurrence relations is correct representation of the towers of Hanoi problem that was discussed in the exploration?

• F(n) = nF(n-1) + 1
• F(n) = 2F(n-1)
• F(n) = 2F(n-1) + 1
• F(n) = F(n-1) + 2

Answer 10

• F(n) = 2F(n-1) + 1