?Suppose you plan to use Indexed Sequential Search, there are n data items in a file and k subfiles. You may assume that k is roughly n^(1/2).

What is the big-O(g(n)) cost to access any given record if you use sequential search on the index? _____

What is the O(g(n)) cost to access any given record if you use binary search on the index? _____

CHOICES for Fill-in-the-Blanks: blank n/2 n/(2k) n/(2k) + n*log(k) n^2 n/2 n/2 + log(k) n/2 + n*log(k) k/2 + log(k)...or...(log(n) + k)/2...or...n/(2k) + log(k) k/2 + n*log(n) n*k + log(n) n*k + n*log(n) n/k + log(n) n/k + n*log(n) n*log(n) log(n) n*k k or n^(1/2) k^(1/2) m