Computational Equivalence Between the Problems of Sorting and Monotone Reconstruction for Random Permutations
  
Key Words:   
Fund Project:
Author NameAffiliation
Kequan Ding Department of Mathematics
University of Wisconsin-Madison Madison
WI 53706
USA 
Hits: 2191
Download times: 1033
Abstract:
      In this note, it is shown that the monotone reconstruction problem is equi-valent to that of sorting, in the sense of computational complexity. In particular from any given sorting algorithm A, an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m) time and O( m) space cost more than that used in A, and vice versa. As a consequence of this result, it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random permutations is O(nlogn).
Citation:
DOI:10.3770/j.issn:1000-341X.1991.01.001
View Full Text  View/Add Comment