What is the complexity of the time and space of the FP-Growth algorithm?

Question

How to calculate time complexity and space complexity of FP_growth algorithm in Data Mining?

Answer 1

For complexity, you can find part of the answer in this article: "Analysis of complexity" Depth of the first and FP-growth of the APRIORI Implementation "(http://www.liacs.nl/~kosters/complap.ps) (this document is in mail format)

Answer 2

In my opinion, the time complexity should be O (n ² ) if the number of unique elements in the data set is n. Complexity depends on finding paths in the FP tree for each element of the header table, which depends on the depth of the tree. The maximum tree depth is limited to n for each of the conditional trees. Thus, the order is: O (number of elements in the header table * maximum tree depth) = O (n * n).