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

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.