Notes on the complexity of sorting in abstract machines (Q1068551): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q4091421 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Time bounded random access machines / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Upper bounds for sorting integers on random access machines / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5585020 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Notes on the complexity of sorting in abstract machines / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Storage Modification Machines / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A class of algorithms which require nonlinear time to maintain disjoint sets / rank | |||
Normal rank | |||
Revision as of 10:24, 17 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Notes on the complexity of sorting in abstract machines |
scientific article |
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
