Notes on the complexity of sorting in abstract machines (Q1068551)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Notes on the complexity of sorting in abstract machines |
scientific article; zbMATH DE number 3932403
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Notes on the complexity of sorting in abstract machines |
scientific article; zbMATH DE number 3932403 |
Statements
Notes on the complexity of sorting in abstract machines (English)
0 references
1985
0 references
The complexity of sorting with pointer machines and successor-predecessor random access machines is studied. The size of the problem is defined as the length of the problem string. A linear time algorithm is achieved for sorting by pointer machines. For successor-predecessor random access machines linear time is sufficient in a special case.
0 references
pointer machines
0 references
successor-predecessor random access machines
0 references
linear time algorithm
0 references
