How do we calculate the Time complexity and Space complexity of FP_growth algorithm in Data Mining??
2 Answers
According to my understanding, the time complexity should be O(n2) if the number of unique items in the dataset is n. The complexity depends on searching of paths in FP tree for each element of the header table, which depends on the depth of the tree. Maximum depth of the tree is upper-bounded by n for each of the conditional trees. Thus the order is: O (No. of items in header table * maximum depth of tree)= O(n*n).
For the complexity, you can find part of the answer in this paper : "Complexity Analysis of Depth First and FP-growth Implementations of APRIORI" (this paper is in postcript format)
1
