-1
$\begingroup$

Linear Search has O(n) T.C and Binary Search have O(logn) T.C. But how come Linear Search generates fewer page faults? Is there another searching technique that causes a lesser number of page faults than linear search?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Your assumption is wrong. If all data is in memory then there are no page faults. Now assume you have 100 pages, none in memory. Linear search will have on average 50 page faults. Binary search will have a fault for page 50, one for page 25 or 75, one for page 12, 37, 62 or 87, and a few more. The total will be the logarithm of the number of pages, that is 6 or 7.

Now if your data set is so huge that it doesn’t fit into RAM, say four times larger, and you search repeatedly. Linear search will have page faults for half the pages on average. For binary search, there is a huge number of pages that are read repeatedly. For example the middle page on every search, the first and last quarter page on every second search, and so on. Most of the pages visited will be in the least recently used list and cause no page fault, only the very last two or three pages will. So with 8GB of RAM available and 32 GB of data, you won’t have a million page faults per search but two or three.

$\endgroup$
1
$\begingroup$

One approach is Eytzinger layout, which is essentially a breadth-first traversal of the binary search "tree".

Eytzinger layout

The idea is that the items that would be visited first in binary search are located next to each other in memory.

Another option is B-trees, which are designed with page efficiency in mind.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.