edited by
2,633 views
3 votes
3 votes
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 $

??
edited by

1 Answer

Best answer
9 votes
9 votes
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.
selected by

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
2 answers
4
manvi_agarwal asked Sep 3, 2018
648 views
https://gateoverflow.in/?qa=blob&qa_blobid=11583750777176064728Approach please