Can you help me figure out this algorithm?

Question

I'm working on a homework assignment and as a "hint" we are told to find the following algorithm, and then prove it to the necessary answer.

Let L(1), L(2), .., L(k) be sorted lists of n elements each. Give a O(kn logk) space algorithm that supports the O(log n + t) Locate operation, which returns the location of t items.

Ideally, I will be able to use this algorithm to give me some insight into achieving a better solution (which is what the assignment wants), but this less effecient algorithm is supposed to inspire me, but I can't figure it out. Any thoughts or know what this algorithm is? Thanks!

Answer 1

ehh... sounds like... binary search? Wiki

Answer 2

Have you googled for O(kn logk) ? That seems to be a pretty unique big-O signature.

Here's my first result: MergeSort --> http://stackoverflow.com/questions/658502/what-is-the-relation-between-merges-and-number-of-items-in-a-in-k-way-merge/659214#659214

Answer 3

Probably not a sorting function since you already have 2 sorted lists. Sounds like Binary Search to me as well.

Answer 4

I can't seem to find one that gives O(log n + t) time, but I had a thought that might or might not help...

O(kn log k) is the size of a table mapping each possible item to the number of the list containing it. However, using that to find which list to look in still results in a t*O(log n)-lookup time for t elements, so it's not really what's asked for...

Answer 5

I think it asks you to find an inefficient algorithm first, then use that to make an efficient one. It sounds like a linear search of lists, each with a binary search to look through them. It will require O(2t) space, because you need to copy down the "coordinates" of the t items.

Answer 6

Even with that ugly big O notation I think it's a Binary Search problem because you have the sorted lists.

Space complexity remains the same because it's a divide and conquer algorithm,so you won't have problems there.

To be very sure is the t outside the logn, something like O((logn)+t)?