Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6559

Re: on resolving a recursive formula

Show all headers | 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