Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: comp.programming
Subject: on resolving a recursive formula
Date: Wed, 27 Apr 2016 08:14:50 -0300
Organization: Aioe.org NNTP Server
Lines: 45
Message-ID: <86shy7qp5h.fsf@toledo.com>
NNTP-Posting-Host: 2qgpAfNKKNVFtQ8BuAGQfg.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: abuse@aioe.org
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
Cancel-Lock: sha1:Ti7v6wW+fR9SLmAMrqVIQbxpP08=
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.programming:6555

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)