COMP3270 Homework 2 Solution

Please submit as a PDF document using Canvas
Instructions:
1. Think carefully; formulate your answers, and then write them out concisely using English,logic, mathematics and pseudocode (no programming language syntax).
2. Type your final answers using a document editor (e.g., Word) and submit online as aPDF through Canvas.
3. Don’t turn in handwritten answers with scribbling, cross-outs, erasures, etc. If an answeris unreadable, it will earn zero points. Neatly and cleanly handwritten submissions are also acceptable.
(1. 10pts)
Compare the following pairs of functions in terms of order of magnitude. In each case, say whether f(n) = O(g(n)), f(n) = Θ(g(n)), and/or f(n) = Ω(g(n))
f(n) g(n)
a. 100n + logn n +(logn)2
b. logn log(n2)
c. n(logn)2
d. (logn)5
e. n2n 3n
(2. 10pts)
Algorithm Mystery(A: Array [i..j] of integer) i & j are array starting and ending indexes begin if i=j then return A[i] else
k=i+floor((j-i)/2) temp1= Mystery(A[i..k]) temp2= Mystery(A[(k+1)..j] if temp1<temp2 then return temp1 else return temp2
end
(a) (1 pts) What does the recursive algorithm above compute?
(b) (3 pts) Develop and state the two recurrence relations exactly (i.e., determine all constants) of this algorithm by following the steps outlined in L7-Chapter4.ppt. Determine the values of constant costs of steps using directions provided in L5-Complexity.ppt. Show details of your work if you want to get partial credit.

(d) (1 pts) Based on T(n) that you derived, state the order of complexity of this algorithm:
alogbn = nlogba


T(n) =
4. (5 points) Use the substitution method to prove the guess that is indeed correct when T(n) is defined by the following recurrence relations: T(n) = 3T(n/3)+5; T(1) = 5. At the end of your proof state the value of constant c that is needed to make the proof work.
Statement of what you have to prove:

Base Case proof:

Inductive Hypotheses:

Inductive Step:

Value of c:
5. (6 points) Find a counterexample to the following claim:
f(n)=O(s(n)) and g(n)=O(r(n)) imply f(n)− g(n) = O(s(n)− r(n))
6. (16 points) Guess a plausible solution for the complexity of the recursive algorithm characterized by the recurrence relations T(n) = T(n/2)+T(n/4)+T(n/8)+T(n/8)+n; T(1) = c using the Substitution Method. (1) Draw the recursion tree to three levels (levels 0, 1 and 2) showing (a) all recursive executions at each level, (b) the input size to each recursive execution, (c) work done by each recursive execution other than recursive calls, and (d) the total work done at each level. (2) Pictorially show the shape of the overall tree. (3) Estimate the depth of the tree at its shallowest part. (4) Estimate the depth of the tree at its deepest part. (5) Based on these estimates, come up with a reasonable guess as to the Big-Oh complexity order of this recursive algorithm.
Your answer must explicitly show every numbered part described above in order to get credit.

7. (10 points) Use the Substitution Method to prove that your guess for the previous problem is indeed correct.
Statement of what you have to prove:

Base Case proof:

Inductive Hypotheses:

Inductive Step:

8. (9 points) Use the Master Method to solve the following three recurrence relations and state the complexity orders of the corresponding recursive algorithms.
(a) T(n) = 2T(99n/100)+100n
(b) T(n) = 16T(n/2)+ n3lgn
(c) T(n) = 16T(n/4)+ n2
9. (10 points) Use Backward Substitution (10 points) and then Forward Substitution (10 points) to solve the recurrence relations T(n) = 2T(n − 1) + 1; T(0) = 1. In each case, do the following: (1) Show at least three expansions so that the emerging pattern is evident. (2) Then write out T(n) fully and simplify using equation (A.5) on Text p.1147. (3) Verify your solution by substituting it in the LHS and RHS of the recurrence relation and demonstrating that LHS=RHS.
(4) Finally state the complexity order of T(n).
You must show your work for parts (1)-(3) to receive credit.

10. (5 points) Solve the following recurrence relation. Give an exact solution:
T(n) = T(n −1)+ n/2
;
T(1) = 1
11. (5 points) Prove that T(n), which is defined by the recurrence relation
T(n) = 2T(bn/2c)+2nlog2n
T(2) = 4
satisfies T(n) = O(nlog2n)
12. (4 points). Problem 3.1-3 (p.53) – Explain why the statement “The running time of algorithm is at least O(n2)," is meaningless.