Average case complexity under the universal distribution equals worst- case complexity
type: Item
instance of: scholarly article
title: Average case complexity under the universal distribution equals worst- case complexity
zbMATH Open document ID: 0780.68064
DOI: 10.1016/0020-0190(92)90138-L
author: Ming Li
author: Paul M. B. Vitányi
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 92108
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: uniform distribution
zbMATH Keywords: quicksort
zbMATH Keywords: average NP completeness
zbMATH Keywords: average complexity
zbMATH Keywords: universal distribution
zbMATH Keywords: worst-case complexity
zbMATH Keywords: time complexity
zbMATH Keywords: space complexity
zbMATH Keywords: sorting
MaRDI profile type: Publication
cites work: Q4074808
cites work: Average Case Complete Problems
cites work: Q4385509
cites work: A formal theory of inductive inference. Part II
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
description: scientific article; zbMATH DE number 92108