Concept icon
Concept

Counting the entire recursion tree rather than only one path

At depth d, M<=Cs 8^(-d) and u_d=Theta_C(lambda/2^d). The mode bound and polynomially many interpolation nodes, values and groups give at most s^{O(1)} exp(O_C((s/sqrt(lambda))(sqrt(2)/8)^d)) children per call. Multiply these branching bounds across depths to bound each level, then sum over O_C(log lambda) levels. The geometric exponents sum to O_C(s/sqrt(lambda)); the polynomial factors add O_C(lambda log lambda) in the exponent. That latter term is smaller asymptotically, so the total number of calls is exp(O_C(s/sqrt(lambda))). The branching bound is independent of the input description length.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math