QR-Code

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+...

Ausführliche Beschreibung

Gespeichert in:
1. Verfasser: Werner Schachinger
Format: Artigo
Sprache:Inglês
Veröffentlicht: Discrete Mathematics & Theoretical Computer Science 2001-01-01
Schriftenreihe:Discrete Mathematics & Theoretical Computer Science
Schlagworte:
recursive algorithms
trie
martingales
asymptotic normality
central limit theorem
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Online-Zugang:https://dmtcs.episciences.org/281/pdf
Tags: Tag hinzufügen
Keine Tags, Fügen Sie das erste Tag hinzu!

Ähnliche Einträge