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

Groups > comp.programming > #6555

on resolving a recursive formula

Show all headers | View raw

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)

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