Suppose we have a function h with m arguments and i.i.d. random variableswith marginal distribution F. Let Hrbe the distribution of einf:,...,Xm), m≥ 2. We consider on-line schemes for estimating quantiles of HF. Such an estimator is based on a design Dn, which is a small subset of all n!/(n-m)! possible index vectors I = (il) having distinct entries not exceeding n. When a new observation Xnarrivesnew vectorswithare used to modify the current estimate. When γ → ∞, the asymptotic relative efficiency of the recursive estimator compared to the off-line estimator (U -quantile) tends to one. The on-line estimator is closely related to incomplete U-quantiles (Hössjer, 1996), and it generalizes a recursive quantile estimator considered by Hoist (1987) for m = 1.