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
    Ech, what might be a better title? Having the title and the tag be identical isn't exactly a great thing...2011-07-27
  • 0
    I don't really understand what the question is trying to say :-). Can you improve the wording a bit?2011-07-27
  • 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.2011-07-27
  • 0
    Thanks @Gerry. That was very clear.2011-07-27
  • 0
    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.2011-07-31
  • 0
    I want to contact the person who answered my question. I am searching their emails on this site page. Unfortunately, i couldn't found. I am sincerely learning the solutions, which are answered by eminent professors. I am once again thankful to them.2011-08-06
  • 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$