The effects of dataset size and search frequency on the computational efficiency of linear and binary search

As datasets grow, the cost of retrieving information becomes increasingly important. This study aims to understand how data size and search frequency affect the comparison counts and execution times of linear and binary search, while also considering the costs of sorting and maintaining ordered data. A Python program compared datasets of 100, 1,000, 10,000, and 1,000,000 elements at search frequencies of 1, 10, 100, and 1,000 searches. Linear search was applied to shuffled datasets, whereas binary search was applied to sorted datasets. For the 1,000,000-element dataset at a frequency of 1,000, the mean comparison count per search was 496,944.9864 for linear search and 18.9492 for binary search, representing a 99.9962% reduction in comparisons with binary search, averaged across 1,000 searches. The reported mean time to insert an element into a sorted Python list increased to approximately 0.116 seconds at 1,000,000 elements. The results illustrated the distinction between search costs on prepared data and the additional costs of sorting or maintaining sorted order. The reported search-time values are retained at their stated precision; their scope (per-search means or batch totals) must be identified before total-runtime conclusions can be finalized. The study relates these findings to the broader use of database indexes.