time complexity optimization

[Pramodmk]

For big trees, the forestdist matrix creation becomes bottle neck. Since the time complexity for the m x n matrix initialization is O(m * n), it increases the overall time taken for treedist method.

Is there any way to optimize this method without affecting the treedistance matrix?

Thanks in advance !

[ijkilchenko]

Reading just the abstract, (here: https://www.researchgate.net/publication/220618233_Simple_Fast_Algorithms_for_the_Editing_Distance_Between_Trees_and_Related_Problems), the time complexity is O(mnmin(depth_m, leaves_m)*min(depth_n, leaves_n)). To clarify notation, depth_i and i signify a tree with i nodes and a depth of depth_i.

That expression is bigger than O(m * n). Creation of the matrix is not the bottle neck. If you do want to optimize that step, you can introduce some sparse matrix library

[Pramodmk]

Reading just the abstract, (here: https://www.researchgate.net/publication/220618233_Simple_Fast_Algorithms_for_the_Editing_Distance_Between_Trees_and_Related_Problems), the time complexity is O(m_n_min(depth_m, leaves_m)*min(depth_n, leaves_n)). To clarify notation, depth_i and i signify a tree with i nodes and a depth of depth_i.

That expression is bigger than O(m * n). Creation of the matrix is not the bottle neck. If you do want to optimize that step, you can introduce some sparse matrix library

Yup, not debating of the time complexity of the algorithm itself. But, the matrix creation itself takes time due to the way java initializes arrays which adds to the overall time complexity.

Using sparse matrix library is indeed interesting idea.