[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

on resolving a recursive formula

Daniel Bastos

4/27/2016 11:15:00 AM

Problem. Express

T(n) = Theta(1) if n = 1
2 T(floor(n/2)) + 17 if n > 1

as a non-recursive formula.

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)

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 vezes)
= 17 + n Theta(1)

The cost of dividing (not the whole cost) of /each/ level i is therefore

2^i Theta(1).

The cost of conquering each level i is always

17.

I have lg(n) levels. Hence my total cost of conquering is 17 lg(n).
Adding all costs I should get

17 lg(n) + Sum(2^i Theta(1), i = 1..k)
= 17 lg(n) + 2^{k+1} - 1

Therefore, my total cost is

T(n) = Theta(n - 1 + 17 lg(n))
= Theta(n)
3 Answers

Ben Bacarisse

4/27/2016 9:28:00 PM

0

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?

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

> 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 vezes)
> = 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.

> The cost of dividing (not the whole cost) of /each/ level i is therefore
>
> 2^i Theta(1).
>
> The cost of conquering each level i is always
>
> 17.
>
> I have lg(n) levels. Hence my total cost of conquering is 17 lg(n).
> Adding all costs I should get
>
> 17 lg(n) + Sum(2^i Theta(1), i = 1..k)
> = 17 lg(n) + 2^{k+1} - 1
>
> Therefore, my total cost is
>
> T(n) = Theta(n - 1 + 17 lg(n))
> = Theta(n)

The above wonders off course again but converges to the right answer.

--
Ben.

Daniel Bastos

4/28/2016 11:23:00 AM

0

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.

Ben Bacarisse

4/28/2016 7:28:00 PM

0

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.