A sequential search is a search algorithm for searching a set of unsorted data for a particular value. In sequential search, we start from the beginning of the list, scan down the list, until the desired key is found or we have reached the end of the end of the list.

• In general, the work required to search sequentially for a record in a file with n records is proportional to n: it takes at most n comparisons; on average it takes approximately n/2 comparisons. It is said to be of the order O(n) because the time it takes is proportional to n.
  
  ^†O(n) means the algorithm is run on some computer on the same type of data but for increasing values of n, the resulting times will always be less than some constant times |n|.


• Blocking, grouping records into blocks, can improve the performance of sequential searches. For example, suppose that we have a file of 4000 records and that the average length of a record is 512 bytes. If the operating system uses a buffer of 512 bytes, on the average, 2000 read calls before it can retrieve a particular record. If there are 16 records per block so each read call brings in 8 KBytes worth of records, the number of reads required for an average search comes down to 125.
  
  ^‡Although blocking can result in substantial performance improvements, it does not change the order of the sequential search operation. The cost of searching is still O(n).


• Sequential searching is just too expensive for most serious retrieval situations. However, it is extremely easy to program, and it requires the simplest of file structures.