Re: on resolving a recursive formula

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: on resolving a recursive formula
Date	Thu, 28 Apr 2016 20:28:06 +0100
Organization	A noiseless patient Spider
Lines	46
Message-ID	<87eg9p4jp5.fsf@bsb.me.uk> (permalink)
References	<86shy7qp5h.fsf@toledo.com> <87zise68sl.fsf@bsb.me.uk> <86potavuxb.fsf@toledo.com>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="26317"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/1kA8M+oioFOcXyQAlR65LokktQmOrTM4="
Cancel-Lock	sha1:KB3NcaNE2/wbpCiTrIha1bjm8/Y= sha1:OFoZyuD30r6acb6bzR7LtkVtOxk=
X-BSB-Auth	1.d2240081a10dac53de03.20160428202806BST.87eg9p4jp5.fsf@bsb.me.uk
Xref	csiph.com comp.programming:6559

Show key headers only | View raw

Daniel Bastos <dbastos@toledo.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Daniel Bastos <dbastos@toledo.com> writes:
>>
>>> Problem. Express
>>>
>>>   T(n) = Theta(1)              if n = 1
>>>          2 T(floor(n/2)) + 17  if n > 1
>>>
>>> as a non-recursive formula.
>>
>> Are you permitted to use what is often called the master theorem?
>
> Yes, I am.  I didn't get it very well, though, so I was trying the
> recursion tree first.  (I'll try to use the master theorem too, but
> after I get a clue about what's going on in T.)
>
> I didn't quite convince myself about the complexity of T.  My first
> thoughts about it were that it should be Theta(n) because although we
> break the work in two halves, we need both answers and the complexity of
> combining both answers is constant --- 17 ---, hence the work of T(n) is
> essentially (n/2 + c) + (n/2 + c) + 17 = n + c = Theta(n).  But this
> agument seems very unclear.

Yes, it is (unclear).  Your answer is right, but the argument is wrong.
I think the key mistake is not expanding the formula correctly.  For
example,

  T(4) = 2T(2) + 17

but since

  T(2) = 2T(1) + 17 = 2Theta(1) + 17

we can say that

  T(4) = 2(2Theta(1) + 17) + 17
       = 4Theta(1) + 3*17

Try with T(8) and then just guess the pattern!

<snip>
-- 
Ben.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

on resolving a recursive formula Daniel Bastos <dbastos@toledo.com> - 2016-04-27 08:14 -0300
  Re: on resolving a recursive formula Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-27 22:28 +0100
    Re: on resolving a recursive formula Daniel Bastos <dbastos@toledo.com> - 2016-04-28 08:23 -0300
      Re: on resolving a recursive formula Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-28 20:28 +0100

csiph-web