PMC:1624833 / 20067-21110 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1624833","sourcedb":"PMC","sourceid":"1624833","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1624833","text":"We now analyze the running time of the algorithm. Let m be the number of ones in the matrix M. As stated earlier, the number of biclusters in the input is n. In Step 1, computing the PQ trees takes O(m) time. Computing the similarity between a pair of PQ trees takes O(c) time, where c is the number of columns of M. Thus, in Steps 2 and 3, computing and sorting the O(n2) similarity values takes O(cn2 + n2 log n) time. We execute Step 4 O(n2) times. The running time of each iteration is proportional to the size of the new PQ tree constructed. A naive upper bound on this size is m, the total number of columns in all the biclusters. Hence, the total running time of Step 4 is O(mn2). Finally, traversing all the PQ trees in T and concatenating the permutations takes O(m) time. Keeping in mind that c ≤ m, the total running time of the algorithm is O(mn2 + n2 log n). The space used by the algorithm is O(m + n2), with O(m) space taken to store all the biclusters and the PQ trees and O(n2) required for Σ, the sorted list of similarities.","tracks":[]}