Asymptotic normality of recursive algorithms via martingale difference arrays
We propose martingale central limit theorems as an tool to prove asymptotic normality of the costs of certain recursive algorithms which are subjected to random input data. The recursive algorithms that we have in mind are such that if input data of size N produce random costs L_N, then L_N=^D L_n+...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Artigo |
| Lenguaje: | Inglês |
| Publicado: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
| Colección: | Discrete Mathematics & Theoretical Computer Science |
| Materias: | |
| Acceso en línea: | https://dmtcs.episciences.org/281/pdf |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|