Swaroop
Swaroop

Reputation: 1299

Understanding time complexity for dynamic indexing

While reading the text, Introduction to Information Retrieval by Manning et al., I came across dynamic indexing (Sec 4.5, Page 79). It consists of two indices, the main index (stored on disk) and an auxiliary index (in-memory), which is merged with the main index once the postings reach a size of n. Assuming the postings in the main index are stored in a single file (T is the size of postings in the main index), it takes O(T^2/n) time to merge the auxiliary index into the main index.

As per the text

In this scheme, we process each posting ⌊T/n⌋ times because we touch it during each of ⌊T/n⌋ merges where n is the size of the auxiliary index and T the total number of postings. Thus, the overall time complexity is Θ(T^2/n).

I am wondering, why it should take O(T^2/n) time to merge the two indices. As per my understanding to merge two sorted arrays should take only O(T+n) time. I am conceptually missing something, would appreciate any help.

Upvotes: 0

Views: 22

Answers (0)

Related Questions