For the following question you must use the following cost estimates. Cost 1. Th

Question

For the following question you must use the following cost estimates. Cost 1. The merging of a list of n sorted elements with a list of m sorted elements has cost n + m. Cost 2. Scanning a list of n elements and performing a constant time operation will cost n. Cost 3. Sorting a list of n elements costs n lgn. Cost 4. Binary search on a list of n sorted elements looking for element x costs lgn. We have three (sorted by docID) doclists for terms A, B, C of length 10, 256.1024 respectively. We would like to perform the following query: A AND B AND C What would the cost of an efficient evaluation be? Use the cost metrics Cost 1, 2, 3, 4 in your analysis.

Explanation / Answer

The logic to solve the problem is very simple.

Look what given is we need to obtain

A AND B AND C i.e. we need to first merge two lists A and B which are already sorted so

cost to merge A and B is n + m and given size of A is 10 and size of B is 256 so 10 + 256 = 266

Now it is nesessary merge A AND B AND C

again cost = n + m here n is 266 and m is 1024 so n +m = 266 +1024 = 1290

Now it is require to sort the updated list which requires the time of nlgn = 1290lg1290 = 9240

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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