Theorem 2 T m; n O mdn , where d 1 log2(1p )
e.

Proof. We analyze the recurrence inequality for any p using considerations similar to those

of Goldberg et al. (1982).

The recurrence inequality takes the form: T m; n  8 : cmn+ (1  mT m; n  1)+ Pm k =1 m k(1  m kT m  k; n  1) m; n  n or m It is easy to show, by induction on n that T m; n grows with n Hence, T m; n  cmn + (1  mT m; n + Xm k =1 m k k(1  m kT m  k; n : (4) solution of (4) is linear in n since this recurrence is linear in the T 0s Now for any value m0 let us choose constant a such that for all m  m0 T m; n  amdn; (5) where d 1 log2(1p ) e Then for all m  m0 (4), (5) imply (1  (1  mT m; n  cmn + Xm k =1 m k(1  m kT m  k; n  cmn + Xm k =1 m k(1  m k m  dn cmn + amdn  Xm k =1 k(1  m k(1  m : As Goldberg et al. (1982) showed,

k
(3)

k

k

m

k

d

m

k

and therefore,

$$\sum_{\begin{array}{c}{{\vphantom{1}}}\\ {{\vphantom{1}}}\end{array}}\qquad\mathrm{~-~}\qquad\mathrm{~-~}\frac{1}{m}\qquad\mathrm{~-~}\qquad\mathrm{~+~}O~m^{-1}~,$$  . 

k

d

+ O m1; (6)
(1  (1  mT m; n  cmn + amdn(1  d+ an  O md 1: cmn O mn), and so,

T m; n amdn(1  d  (1  m + an  O mmax (1;d 1):
We are going now to nd out conditions under which

amdn(1  d  (1  m + an  O mmax (1;d 1)  amdn;
469