min max using divide and conquer

Question

CAN SOMEONE SOLVE THE NUMBER OF COMPARISIONS FOR COMPUTING MIN AND MAX IN AN ARRAY USING DIVIDE N CONQUER??

RECURRENCE RELATION IS

$ T(n) = 2 T(\frac{n}{2}) + 2 $

IT SHOULD COME TO $ \frac{3*n}{2} - 2 $

??

Comments

U want solution by recurrence relation?

Otherwise by taking an example u can chk it.

By the way , is it not

T(n) = 2T(n/2) + 1 

---

Recurrence relation is correct I think. Yeah I want solution by recurrence. It's not coming as expected.

Wats ur solution?

---

Now its look cool.

@Srestha we can tweak D&C algorithm to $+2$ also. That's correct. There is no problem.

Answer 1

To understand, first you have to understand this

$ \sum_{i=0}^{n} 2^i = 2^{n+1} -1 $
or $ \sum_{i=1}^{n} 2^i = 2^{n+1} -2 $

Now Come to your recurrence, let $ n = 2^k $

$ T(n) = 2T(\frac{n}{2}) + 2 $

      $  = 2 (2 T(\frac{n}{4}) + 2) + 2 $

      $  = 2^2 T(\frac{n}{ 2^2 }) + 2^2 + 2 $

      $  = 2^3 T(\frac{n}{ 2^3 }) + 2^3 + 2^2 + 2 $

      $  = 2^4 T(\frac{n}{ 2^4 }) + 2^4 + 2^3 + 2^2 + 2 $

      $ --------------------------------- $

      $ --------------------------------- $

      $  = 2^{k-1} T(\frac{n}{ 2^{k-1} }) +2^{k-1} + ------------ +  2^3 + 2^2 + 2 $

      $  = 2^{k-1} T(\frac{2^k}{ 2^{k-1} }) +2^{k-1} + ------------ +  2^3 + 2^2 + 2 $,  Since $ n = 2^k $

      $  = 2^{k-1} T(2) +2^{k-1} + ------------ +  2^3 + 2^2 + 2 $

      $  = 2^{k-1} * 1 +2^{k-1} + ------------ +  2^3 + 2^2 + 2 $, Since $ T(2) = 1 $

      $  = 2^{k-1} +2^{k-1} + ------------ +  2^3 + 2^2 + 2 $

      $  = 2^{k-1} + \sum_{i=1}^{i = (k-1)} 2^i $

      $  = 2^{k-1} +2^{k} - 2  $

      $  = \frac{n}{2} + n - 2  $ , Since $ n = 2^k $ ==> $ k = log 2 $

$ T(n) = \frac{3*n}{2} - 2 $

Hence Solved.

Comments

@sushmita

---

Thanx @ Rude. Got the solution. :)