EXPECTED WORST-CASE PARTIAL MATCH IN RANDOM QUADTRIES

Let Nn(y) be the complexity of the standard partial match algorithm for fixed vector y, where y is a vector in Rs,0< s < d. We study Nn = supy Nn(y), the worst-case time for partial match. Among other things, we show that partial match is very stable, in the sense that sup yN n(y)/inf N (y) → 1 in probability. Keywords and phrases. ................
................