I am trying to implement LCA of multiple nodes in an n-ary tree in java. I am working with parse trees of sentences, So its reasonable to assume that number of children of a node <= 6. Multiple nodes here are two phrases(continuous word sequence) in a sentence. Let k be the number of nodes involved.

One way is to find the LCA of two nodes for k/2 pairs and we will get k/2 nodes. Now recurse on these k/2 nodes. The order will be O(nlog k), where O(n) is the complexity of linear LCA finding algorithms. Can I do it more efficiently ?