# Recurrence Relation for max and min of a sequence

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

-
Ech, what might be a better title? Having the title and the tag be identical isn't exactly a great thing... –  Guess who it is. Jul 27 '11 at 6:37
I don't really understand what the question is trying to say :-). Can you improve the wording a bit? –  Srivatsan Jul 27 '11 at 6:42
@Srivatsan, I think the question is trying to say, calculate $f(128)$, given $f(1)=0$ and $f(n)=2f(n/2)+2$. OP got 14, but wherever OP found the (multiple-choice) problem the options offered were 126, 128, 254, and 255. So OP wants to know what went wrong. –  Gerry Myerson Jul 27 '11 at 7:23
Thanks @Gerry. That was very clear. –  Srivatsan Jul 27 '11 at 7:25
You still here, MahimA? You've asked quite a few questions, haven't accepted any answers, haven't had any input on this question since asking it. –  Gerry Myerson Jul 31 '11 at 9:45

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.

-

$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$

-