1
$\begingroup$

Please observe the following How many comparisons are needed to locate the Maximum and minimum elements in a sequence of 128 elements. Using the following :

$f(n) = 2 f(n/2) + 2,$ where $f(1) =0$.

My work:

$f(n) = 2 f(n/2)+ 2$

If this is a divide by $2$ { binary divide , I think } then there are a sequence of $128$ elements, this must be $n$?

$f(n)= 2f(128/2)+ 2;$ if I keep dividing by $2$, I come to

$2f(1) + 14;$ SUB $0$ for $f(1)= 0$ ...as stated above

then $2 (0) +14 = 14$ comparisons.

yet my choices are $126, 128, 254, 255$.

where did I go wrong , hope you can help , if I need to resubmit showing all divide by $2$, I will...

thank you

Mahima

  • 0
    The way to thank someone on this website is to click the little up-arrow next to the answer(s) you like, and to click the check-mark in the answer you like the best.2012-02-19

2 Answers 2

3

You went wrong at the second step, going from $f(64)$ to $f(32)$ you dropped the multiplier of 2 in $f(n)=2f(n/2)+2$.

Might be easier to start at the bottom and work your way up: $f(1)=0$; $f(2)=2f(1)+2=(2)(0)+2=2$;
$f(4)=2f(2)+2=(2)(2)+2=6$; etc., etc.

1

$T(n) \implies 2T(n/2) + 2 = \frac{3n}{2}-2$

You can prove this formula by induction:

Base case: You know that when $n=2$ you just need $1$ comparison. Plug it in the formula and check for yourself.

Next, assume it is true for some $k$ and prove it is true for $k+1$.

How will I get to this formula in exam? You can "easily" derive this:

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

$= 2(2T(n/4) + 2) + 2 $

$= 2^2T(n/2^2) + 2^2 + 2$

$\vdots$

Eventually you will get,

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

$= n/2 + 2(n/2 − 1)$

$= \frac{3n}{2}-2$