PAGE FAULTS

Question

Consider a binary search algorithm to search an element in array of ‘n’ numbers. Assume that this array spans over multiple pages with each page holding ‘p’ elements (n>p). Every memory access will generate a page fault until the search range is less than ‘p’. The minimum value of ‘p’ that reduces the page fault is

Answer 1

1.   n
   Explanation:
   We have n elements and a page can hold p elements. So, we will have n/p pages to store elements and binary search takes log(n/p) memory accesses. 
   Each memory access creates a page faults. So we have log(n/p) page faults. 
   To minimize page faults partial differentiate it with p and n then equate it to zero. 
   We get p=n or to minimize p value use the method below:
   The minimum value of page fault would be zero (ideal) then if we put p=n then we get log(n/p) = log(n/n) = log1=0.