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

Groups > comp.programming > #6556

Re: on resolving a recursive formula

Show all headers | View raw

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.

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