1. [5 pts]: What is the worst-case big-O asymptotic running time of the following method mthd, assuming that the parameter n is a positive integer? Assume that the time complexity of addition is logarithmic in the magnitude of the number. Justify your answer.

void mthd ( int n ) {

int answer = 0;

for ( int i = 1; i

for ( int k = 1; k

answer += i + k;

}

}

for ( int m = 1; m

answer += m;

}

}

Solution:

2. [5 pts]: Consider that f(n) = n + n lg n is Q(n lg n) by applying the definition of Q-complexity from Chapter 3 of Cormen (reproduced below).

Definition: (g(n)) = { f(n) : there exists positive constants c₁, c₂, n₀ such that 0 c₁g(n) f(n) c₂g(n) , for n n₀}. Find a (c₁, c₂, n₀) triple that meets the criteria. Show some work.

Solution:

3. [5 pts]: Consider the following binary min-heap, with the array representation as shown. Note that I chose to start with array index 1, as is traditional with heaps.

Value	1	2	4	14	19	20	7	18	30
Index	1	2	3	4	5	6	7	8	9

1. [3 pts] Show the array implementation of the heap after extracting the root (you may, but need not, choose to draw the new heap as well.

Part (a) solution:

Value
Index	1	2	3	4	5	6	7	8

2. [2 pts] Show the array implementation of the original heap after adding 12 and putting it in the appropriate spot.

Part (b) solution:

Value
Index	1	2	3	4	5	6	7	8	9	10