The Probability Spaces of QuickSort
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913902993866752 |
|---|---|
| author | Nadareishvili, George Oberhauser, Jonas Paul, Wolfgang J. |
| author_facet | Nadareishvili, George Oberhauser, Jonas Paul, Wolfgang J. |
| contents | QuickSort and the analysis of its expected run time was presented 1962 in a classical paper by C.A.R Hoare. There the run time analysis hinges on a by now well known recurrence equation for the expected run time, which in turn was justified by referring to ``the law of conditional expectations''. A probability space for the runs of the algorithms was not constructed. Subsequent textbooks treated the recurrence relation as self evident and present it until this day without proof. Here we give an inductive definition of the probability space for the runs of randomized QuickSort and subsequently derive the recurrence equation with a not completely trivial proof. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04133 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Probability Spaces of QuickSort Nadareishvili, George Oberhauser, Jonas Paul, Wolfgang J. Computational Complexity Probability QuickSort and the analysis of its expected run time was presented 1962 in a classical paper by C.A.R Hoare. There the run time analysis hinges on a by now well known recurrence equation for the expected run time, which in turn was justified by referring to ``the law of conditional expectations''. A probability space for the runs of the algorithms was not constructed. Subsequent textbooks treated the recurrence relation as self evident and present it until this day without proof. Here we give an inductive definition of the probability space for the runs of randomized QuickSort and subsequently derive the recurrence equation with a not completely trivial proof. |
| title | The Probability Spaces of QuickSort |
| topic | Computational Complexity Probability |
| url | https://arxiv.org/abs/2504.04133 |