I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm.
Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A list of frequent closed itemsets are frequent items that appear several times in a set of transactions (tids) (e.g. bread and milk are items often purchased together), they are obtained by cycling the current element with index i with n- 1 successive elements in the inner for whose index will always be j = i + 1. The algorithm is based on 3 properties and depending on the case there can be a replace on the set of the array of items P and any new set of objects generated Pi, all this depends on the transactions (tids), some examples of the properties are the following:
- I have an array of items -> A with 1345 transactions, an item D with tids 1356, F - 1345, E - 12345
- Comparison A with the next elements sorted by support (number of tids present for A is 4, for E it is 5 etc.)
- I compare A with D and I fall back into property 3 since the tids of A are not the same as those of B (Property 1), nor are they contained (Property 2); then add in Pi AD - 135
- Comparison A with F, they have the same tids (Properties 1), I replace A with AF - 1345 in P by removing the old A, in Pi we cycle by performing the replace also on Pi
- I compare AF (as it has been replaced) with E and I fall into Property 2 where the tids 1345 are a subset of those of E -12345; I replace AF with EFE - 1345 in P and I replace also in Pi
Run the inner loop if the set Pi is not empty I recursively execute CHARM on the objects generated in Property 3 otherwise I add the generated Xi's and filtered by minsup (minimum support. For example if I set it equal to 3 I reject the elements that do not reach 3 tids, e.g. a hypothetical H - 1 6 is discarded) in the set C (Frequent closed itemset) if this element is not a subset of one of those present. Here is a practical example with initial dataset and resolution:
It can be seen that the Xi DEB has tids 135 and would not be added in C as a subset of ADEB which has the same tids. To see the resolution graphically, just see the following video of a few minutes https://www.youtube.com/watch?v=XTj53ctgFFk. From my analysis the complexity should depend on the average length of the tids l and on the set Pi passed in recursion but I'm not sure, how is the following recursive algorithm solved to get the running time?
