1
$\begingroup$

I'm currently working on an exercise that has made me ponder for a bit. The following exercise is from the 6th Edition of Data Structures and Algorithms in Java:

An inverted file is a critical data structure for implementing applications such an index of a book or a search engine. Given a document D, which can be viewed as an unordered, numbered list of words, an inverted file is an ordered list of words, L, such that, for each word w in L, we store the indices of the places in D where w appears. Design an efficient algorithm for constructing L from D.

I decided to go with a multimap. It is my understanding that my algorithm could work by "reading" D and putting each word as key and its position as value in the map. Because it is a multimap, this would mean that it doesn't matter if it's encountered the word before, since the previous value(s) wouldn't be lost. Then by the end of "reading", the algorithm will have created a map where it would be easily accessible to find a word we're looking for in the text, could return all the positions of the word, etc. And since put(k,v) takes $O(1)$ time, then for $n$ words that would be $O(n)$ time.

I would like for someone to explain the following things, so that I can understand a bit more:

  1. Because it sounds like a simple solution I'd like to make sure it's a correct one.
  2. $O(n)$ sounds like an awful lot when the D file contains a lot of words. Does this solution limit it to smaller files too much?
  3. Lastly, is there another way to implement this that is more efficient? It doesn't matter if the method is unknown to me, I'm just curious about it.
$\endgroup$
5
  • 2
    $\begingroup$ If your multimap uses hashing then I think that would give you $O(1)$ expected time per insert hence $O(n)$ expected time in total. Since you need to process $n$ words, then your algorithm needs at least $n$ steps. $\endgroup$
    – Russel
    May 31, 2022 at 0:06
  • $\begingroup$ What do you call $n$ ? The total number of words or the number of distinct words ? Obviously, no algorithm can perform faster than the total number of words. $\endgroup$
    – user16034
    May 31, 2022 at 10:33
  • $\begingroup$ @YvesDaoust Yes, i was referring to total number of words. $\endgroup$
    – Tita
    May 31, 2022 at 13:10
  • $\begingroup$ So "$O(n)$ sounds like an awful lot" is a nonsense. It's just the input size. $\endgroup$
    – user16034
    May 31, 2022 at 14:37
  • $\begingroup$ @YvesDaoust Okay. $\endgroup$
    – Tita
    May 31, 2022 at 14:39

1 Answer 1

2
$\begingroup$

Since you have $n$ word, the put(k,v) operation needs to be done at least $n$ times. Let's say you have an algorithm that process $D$ in $o(n)$. The algorithm is not considering some words, hence it's not working properly. That's because words have not an ordering or a property that can let any algorithm "skip" some words.

Also, I don't think $O(n)$ is awful, in this case it's the best we can do :)

$\endgroup$
2
  • $\begingroup$ Haha, maybe it's because I'm used to hearing that $O(n)$ is too much in other cases that I can't comprehend it might be the best case for other situations~ Thanks for the input. $\endgroup$
    – Tita
    May 31, 2022 at 13:11
  • 1
    $\begingroup$ You will have a lower bound of O(n) in the input size if you can show that you need to read the complete input to guarantee that you get the correct result. Example: If you want to find the largest of n numbers, you MUST read all n numbers, because if you ignore just one of the numbers, that might or might not be the largest one, and you can't know. Therefore it's at least O(n). Now if you wrote a program that checks if a number n is a prime number in Theta(n), that would be awfully bad. $\endgroup$
    – gnasher729
    May 31, 2022 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.