# Computing RF Tree Distance over Succinct Representations
## 4 Implementation
### Time and Memory Analysis  
We also implemented the Day algorithm so that we could compare it with our implementation in terms of running time and memory usage. This algorithm was also implemented in C++. It stores two vectors of integers with size \(n\) for each tree and two vectors of integers with size \(n/2\) (the number of leaves). The complexity of the algorithm is \(O(n)\) with respect to both time and space.  
The complexity of both parsing phases, namely the Day approach and our approach, is \(O(n)\), since they loop through all the nodes. The complexity of the Day algorithm with respect to the RF computation phase is also \(O(n)\). With respect to the second phase of our approach, we depict the complexity analysis with respect to the number of times LCA, NumLeaves, ClusterSize, PostOrderSelect and NextSibling are called and which depends on \(n\).  
For RF computed with rf_postorder implementation, the PostOrderSelect operation is called for each node \(n\) times. The number of times LCA is called is equivalent to the number of leaves minus the number of first leaves which in the worst case is \(n-2\). This case would be a tree that only contains the root as an internal node. With respect to NumLeaves operation, it is called two times for each internal node, with the worst case being \(2\times(n-1)\). This case is when a tree only has one leaf. ClusterSize operation is called one time for each internal node, which results in \(n-1\) in the worst case as before. In total, the complexity is \((n+(n-2)+(2\times(n-1))+(n-1))\times O(\log(n))=(5n-5)\times O(\log(n))\). However, the worst case for LCA operations is the best case for NumLeaves and ClusterSize and vice versa. This means that in the worst case, LCA operation is applied 0 times and the complexity is \((4n-3)\times O(\log(n))\)).  
For RF computed with rf_nextsibling implementation, the number of calls for LCA and NumLeaves is the same as before. The number of NextSibling operation calls is the same as that of LCA operation. This means that the complexity for this case is \(((n-2)+(n-2)+(2\times(n-1)))\times O(\log(n))=(4n-5)\times O(\log(n))\); however, for the same reason as before, it can be reduced to \((2n-2)\times O(\log(n))\).  
For the wRF distance computed by both rf_postorder and rf_nextsibling implementations, the number of times these operations are called is the same as that of the original RF. For eRF and weRF computed by both implementations, the only difference is that the LCA operation is called also for all internal nodes. This means that the number of times the LCA operation is applied is equivalent to the total number of nodes minus the number of first leaves. This changes the complexity in both implementations. In rf_postorder, it changes to \((5n-4)\times O(\log(n))\) since the number of LCA calls passes from 0 to \(n-1\) in the worst case. In rf_nextsibling, it changes to \((3n-3)\times O(\log(n))\). All implementations referred above have then a running time complexity of \(O(n\log(n))\).  
In terms of memory usage, RF computed by both rf_nextsibling and rf_postorder implementations only uses two bit vectors of size \(2n\) and a vector of 32 bit integers with size \(n\), so the total of bits used is \(36n\) bits; however, the last one needs an additional stack to save LCA values. And the efficient implementation of prime operations over the bit vectors require extra \(o(n)\) bits. The Day algorithm (rf_day implementation) needs four vectors of 32 bit integers with size \(n\) as well as two vectors of 32 bit integers with the size equal to the number of leafs which is equal to \(n-1\) in the worst case. This results in \(32\times 4n+32\times 2(n-1)=192n-64\) bits.