?Suppose you plan to use Indexed Sequential Search, there are n data items in a

Question

?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

Explanation / Answer

Solution:

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

In this case, the complexity will be

T(n)= n*k

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

In this case, the complexity will be

T(n)= n/2 + n*log(k)?

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.