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

Groups > comp.programming > #6557

Re: on resolving a recursive formula

Show all headers | View raw

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.

>> Solution.  Following the steps of Cormen et al, ``[w]hen we state and
>> solve recurrences, we often omit floors, ceilings, and boundary
>> conditions.'' -- Introduction to Algorithms, Cormen at al, page 88, 3rd
>> edition.  (I also assume n is a power of 2 --- page 94, last paragraph,
>> 3rd edition.)
>>
>> So, for n > 1,
>>
>>   T(n) = 2 T(n/2) + Theta(1)
>
> That's true but just adds confusion.  I'd leave the 17 there.

Okay.

>> Doing the recursion tree, I observe that
>>
>>   level 1: 17 + T(n/2) + T(n/2)
>>          = 17 + 2 T(n/2)
>>   level 2: 17 + T(n/4) + T(n/4) + T(n/4) + T(n/4)
>>          = 17 + 4 T(n/4)
>>   ... 
>>   level k: 17 + Theta(1) + ... + Theta(1) (n [times])
>>          = 17 + n Theta(1)
>
> This is not right.  The "recursion tree" is not easy in a text-based
> medium but you are not correctly writing the levels nor the additive
> part which is usually put off to one side.

Yes, I didn't write the addition of each level on the right, as the book
does.  I'm perceiving now that's one of my questions.  How could I know
what each level adds up to?  For instance, in level 1, I don't know the
cost of T(n/2), so how should I know what 17 + 2 T(n/2) adds up to?
Isn't that what I'm trying to discover in the first place?

[...]

Thank you for your attention.

Back to comp.programming | Previous | Next — Previous in thread | Next 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