Suppose we have market baskets that satisfy the following assumptions:
1. The support threshold is 10,000.
2. There are one million items, represented by the integers 0, 1, . . . , 999999.
3. There are N frequent items, that is, items that occur 10,000 times or more.
4. There are one million pairs that occur 10,000 times or more.
5. There are 2M pairs that occur exactly once. Of these pairs, M consist of two frequent items; the other M each have at least one non frequent item.
6. No other pairs occur at all.
7. Integers are always represented by 4 bytes.
Suppose we run the A-Priori Algorithm and can choose on the second pass between the triangular-matrix method for counting candidate pairs and a hash table of item-item-count triples. Neglect in the first case the space needed to translate between original item numbers and numbers for the frequent items, and in the second case neglect the space needed for the hash table.
As a function of N and M, what is the minimum number of bytes of main memory needed to execute the A-Priori Algorithm on this data?