Algorithm
is as follows:
1.pick
any leaf in the tree, and name it as L1
2.find
the longest path from L1 in the tree. We name the leaf at the other end of the
path as L2. The complexity of this step is θ(m), where m =
c*n(0.5≤c≤1).
3.find
the longest path from L2 in the tree. We name the leaf at the other end of the
path as L3. This path(from L2 to L3) is the longest path in the whole tree. The
complexity of this step is θ(n).
Therefore,
the complexity of the whole algorithm is θ(m+n).
In
the best case scenario, m=0.5*n, thus the total complexity is θ(1.5*n)=
θ(n).
In
the worst case scenario, m=n, thus the total complexity is θ(2*n) =
θ(n).
So
the complexity of the whole algorithm is θ(n).
Prove: the key of the prove is to demonstrate that L2 must be one of the leaves on the longest path.
Assuming
there is a path(P’) which is longer than the path(P) we get from the algorithm,
and L2 is not one of the leaves on this path. We name the 2 leaves on the
longest path as x and y.
Condition1:
P and P’ have a common node like figure as follows:
*We ignore the other nodes, edges, and leaves in the tree.
Py P1 P2 Px y x L2 L1
P=P1+P2, P’=Px+Py,
Based on assumption, Px+Py>P2+P1, and Px+Py>Px+P2àPy>P2à P1+Py>P1+P2, this is a contradiction to the condition that P(P1+P2) is the longest path from L1.
P0 Px Py P2 P1 x y L1 L2
Condition1:
P and P’ have no common node but are connected through path P0(P0>0):
Based on assumption, Py+Px>Py+P0+P2.
Since P2+P1 is the longest path from L1, P1+P2>P1+P0+Px.
So Py+Px+ P1+P2> Py+P0+P2+ P1+P0+PxàP0<0, this is a contradiction.
Conclusion: L2 must be one of the leaves on the longest path.