For the queries below, can we still run through the intersection in time O(x + y), where x and y are the lengths of the postings lists for Brutus and Caesar? If not, what can we achieve? (Please refer Figure 1.3 on page 6 of the textbook.) (20 points)

a. Brutus AND NOT Caesar

b. Brutus OR NOT Caesar

Please solve a & b.

Reference Figure from text book is shown below

Brutus 1 2 4 11 31|45 173174 Caesar 1 24 5616 57 132. Calpurnia2 31 54 101 Dictionary Postings Figure 1.3 The two parts of an inverted index. The dictionary is commonly kept in memory, with pointers to each postings list, which is stored on disk