DocumentCode
1025699
Title
On the complexity of search algorithms
Author
Chung, Kuo-Liang ; Chen, Wen-Chin ; Lin, Ferng-Ching
Author_Institution
Dept. of Inf. Manage., Nat. Taiwan Inst. of Technol., Taipei, Taiwan
Volume
41
Issue
9
fYear
1992
fDate
9/1/1992 12:00:00 AM
Firstpage
1172
Lastpage
1176
Abstract
The average complexity for searching a record in a sorted file of records that are stored on a tape is analyzed for four search algorithms, namely, sequential search, binary search, Fibonacci search, and a modified version of Fibonacci search. The theoretical results are consistent with the recent simulation results by S. Nishihara and N. Nishino (1987). The results show that sequential search, Fibonacci search, and modified Fibonacci search are all better than binary search on a tape
Keywords
computational complexity; search problems; Fibonacci search; average complexity; binary search; modified Fibonacci search; record searching; search algorithms; sequential search; sorted file; tape storage; Algorithm design and analysis; Compaction; Computer languages; Conferences; Costs; Magnetic heads; Notice of Violation; Optimizing compilers; Time factors; Timing;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.165398
Filename
165398
Link To Document