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: Wed, 27 Apr 2016 22:28:26 +0100
Organization: A noiseless patient Spider
Lines: 60
Message-ID: <87zise68sl.fsf@bsb.me.uk>
References: <86shy7qp5h.fsf@toledo.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="22450"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18MwAiuuqxWVWufBNFLZ8wlUxQqHg8GPeI="
Cancel-Lock: sha1:kzejIv70CZ8JYRQcw+lz4ozXmo4= sha1:+Uk4y2GfzkhfGedK7phxm9fDtYc=
X-BSB-Auth: 1.17eec73ea83aea7a4975.20160427222826BST.87zise68sl.fsf@bsb.me.uk
Xref: csiph.com comp.programming:6556

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.