Physical Sciences and Mathematics Commons^™

Analysis Of A Recurrence Arising From A Construction For Nonblocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers n > 1 by the recurrence f(n) = min( n, min_m|n( 2f(m) + 3f(n/m) ). The function f has f(n) = n as its upper envelope, attained for all prime n.

The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form f(n) ~ C(log n)^{1 + 1/γ} for certain constants γ and C, in the sense that for any ε > 0, the inequality f(n) ≤ (C + ε)(log n)^{1 + 1/γ} holds for infinitely many n, while f(n) ≤ (C + ε)(log …