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 …

Analysis Of A Recurrence Arising From A Construction For Non-Blocking 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 ) \sim C( \log n )^{1 + 1/\gamma } $ for certain constants $\gamma $ and C, in the sense that for any $\varepsilon > 0$, the inequality $f( n ) \leq ( …