From: spuler@coral.cs.jcu.edu.au (David Spuler)
Subject: Recurrence relations
Organization: James Cook University
Date: 18 Nov 92 02:36:17 GMT


Can anyone help me solve the following two recurrence relations?
They are both derived from optimal binary trees and must be minimized.

I'm a PhD student in Computer Science, at James Cook University, Australia,
and any help on these issues would improve my thesis.


RECURRENCE A:
  c[0] = 0
  Generally, c[n] is minimum of 3 cases:
    c[n] = c[n-1]            + alpha * n                      ; Case 1
    c[n] = c[i]     + c[n-i] + alpha * n  (with 1<=i<n)       ; Case 2
    c[n] = c[i - 1] + c[n-i] + beta * n   (with 1<=i<n)       ; Case 3


RECURRENCE B:
  c[0] = 0
  Generally, c[n] is minimum of 2 cases:
    c[n] = c[n-1]            + alpha * n                      ; Case 1
    c[n] = c[i]     + c[n-i] + beta * n      (with 1<=i<n)    ; Case 2


Both of these recurrences can be simplified to change the two parameters alpha
and beta to use only one parameter:

  R = beta/alpha

Dividing all terms gives the new equivalent recurrences:

RECURRENCE A2:
  c[0] = 0
  Generally, c[n] is minimum of 3 cases:
    c[n] = c[n-1]            + n                      ; Case 1
    c[n] = c[i]     + c[n-i] + n       (with 1<=i<n)  ; Case 2
    c[n] = c[i - 1] + c[n-i] + R * n   (with 1<=i<n)  ; Case 3


RECURRENCE B2:
  c[0] = 0
  Generally, c[n] is minimum of 2 cases:
    c[n] = c[n-1]            + n                      ; Case 1
    c[n] = c[i]     + c[n-i] + R * n (with 1<=i<n)    ; Case 2


CONJECTURE 1:  cut-offs for Case 1
--------------------------------------

I have empirical evidence to support the conjecture that Case 1 is only
chosen for small n, and for some cut-off point k, we have n>=k implying
that only Case 2 (or 3 for recurrence A) is applicable.
Can anyone help me prove this?

Is there an analytical formula for the cut-off?
For recurrence B I have a theoretical approximate value of

k ~=~ 4R 

which I derived by noting that if my conjecture is true, then

n <= k  ====> c[n] = 1/R * n(n+1)/2


CONJECTURE 2:  Choice of i for case 2/3
--------------------------------------

I also have the conjecture backed up by empirical evidence that if Case 3 
is chosen in Recurrence A, or Case 2 in Recurrence B, then the best choice of
i is ceil(n/2)  (equivalently floor, doesn't matter which).
However, Case 2 in Recurrence A seems not to always be i==n/2, although it
is always reasonably close to that value.
Can anyone help me prove this..

---------------------------------------------------------

Perhaps this will help ......
These recurrences are all generalizations of a simpler recurrence about which
I posted a query a while ago.  That recurrence was:

c[0] = 0
c[n] = c[n - 1]  + n         Case 1
c[n] = c[i] + c[n-i] + n     Case 2

Thanks to a few great responses the exact solution was derived as:

c[n] = a(b+4) + (3b+6) 2^b,   where n is parameterized as:  n= a + 3*2^b
equivalently:  c[n] = 2a + (b+2)n

This also helped prove similar conjectures to above, i.e that for n>=5 the
best choice was always case 2 (i.e. the cut-off was k=4), and also that the
best choice of i for case 2 was i=floor(n/2).
This recurrence is the same as Recurrence B with R=1, or Recurrence A without
Case 3.

---------------------------------------------------------

More details are available on request.  I look forward to any useful responses
with hints, tips, or even pointers to papers/books which will help me solve
such minimization recurrences  (e.g. I've looked at Greene/Knuth's book
"Mathematics for the Analysis of Algorithms" but my recurrences are more
difficult than the one's they examine).

Thanks in advance,
David Spuler