Assuming n is a power of 2, write down a recursivedivide-and-conquer algorithm f
ID: 3608694 • Letter: A
Question
Assuming n is a power of 2, write down a recursivedivide-and-conquer algorithm for solving
the “simultaneous minimum and maximum”problem. Make sure you give enough details that,
based on your description, any competent programmer could easilyimplement it. If we let T(n) denotethe number of comparisons done by your algorithm,
write down the recurrence relation satisfied by T(n). Solve exactly (withoutusing the “big O” notation) the recurrence relation forT(n), by
(a) using the algebraic method described in class to“guess” what the solution is
(repeatedly using the recurrence until apattern appears), and then
(b) proving the correctness of your answer by induction onn.
Assuming n is a power of 2, write down a recursivedivide-and-conquer algorithm for solving
the “simultaneous minimum and maximum”problem. Make sure you give enough details that,
based on your description, any competent programmer could easilyimplement it. If we let T(n) denotethe number of comparisons done by your algorithm,
write down the recurrence relation satisfied by T(n). Solve exactly (withoutusing the “big O” notation) the recurrence relation forT(n), by
(a) using the algebraic method described in class to“guess” what the solution is
(repeatedly using the recurrence until apattern appears), and then
(b) proving the correctness of your answer by induction onn.
Explanation / Answer
Dear User,
T (2) = 1. If n > 2 then T (n) = 2T (n/2) +2.
(a) T(n) = 2T(n/2)+2 = 2(2T(n/22)+2)+2 = . . .=2iT(n/2i)+2i+2i-1+·· ·+2
If, in the above, welet Si denote 2i + 2i-1 + ·· · + 2, then
2Si = 2i+1 + 2i + ·· · + 22 = 2i+1 + Si 2.
ThereforeSi = 2i+1 2 and the recurrencebecomes
T(n) = 2iT(n/2i) + 2i+1 2.
When n/2i equals 2, the above becomes
T(n) = (n/2)T(2) + n 2 = (3n/2) 2.
(b) Basis of induction. For n = 2 the right-hand-side is (3*2/2) 2 = 1, which is T(1) as required.
Inductive step. Inductive hypothesis: Assume the claim holds upto (and including) n. To show that it must also hold for 2n, notethat the recurrence relation and inductive hypothesis imply thefollowing:
T(2n) = 2T(n) + 2 = 2((3n/2) 2) + 2 = 3n 4 + 2 =3n 2 = 3(2n)/2 2.
I hope this will helps toyou