Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Ech, what might be a better title? Having the title and the tag be identical isn't exactly a great thing... –  J. M. 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
1  
@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

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.