How to compute a least common ancestor algorithm's time complexity?

Question

I came into an article which talking about the LCA algorithms, the code is simple http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return LCA(root->left, p, q);
  else /* totalMatches == 0 */
    return LCA(root->right, p, q);
}

but I was wondering how compute the time complexity of the algorithm,can anyone help me?

fwiw: Lowest Common Ancestor can also be found in O(1) if you can pre-compute for all nodes (in O(n) time) https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm — Asad Iqbal, Sep 17 '16 at 21:22

score 4 · Answer 1 · edited May 23 '17 at 12:00

4

The complexity of LCA is O(h) where h is the height of the tree. The upper bound of the tree height is O(n), where n denotes the number of vertices/nodes in the tree.

If your tree is balanced, (see AVL, red black tree) the height is order of log(n), consequently the total complexity of the algorithm is O(log(n)).

edited May 23 '17 at 12:00

Community

1
1

answered Jun 07 '14 at 12:37

0x90

39,472
36
165
245

You counted cost of LCA. But in his implementation, OP traverses the subtree in each call (`h` times) in function countMatchesPQ. So the total complexity should be more than h. Isn't it? – Mohit Jain Jun 07 '14 at 13:11
You are right. That's why we have your answer for :) – 0x90 Jun 07 '14 at 14:31

Mohit Jain · Accepted Answer · 2014-06-25T09:37:02.140

The worst case for this algorithm would be if the nodes are sibling leave nodes.

Node *LCA(Node *root, Node *p, Node *q)
{
  for root call countMatchesPQ;
  for(root->left_or_right_child) call countMatchesPQ; /* Recursive call */
  for(root->left_or_right_child->left_or_right_child) call countMatchesPQ;
  ...
  for(parent of leave nodes of p and q) call countMatchesPQ;
}

countMatchesPQ is called for height of tree times - 1. Lets call height of tree as h.

Now check the complexity of helper function

int countMatchesPQ(Node *root, Node *p, Node *q) {
  Search p and q in left sub tree recursively
  Search p and q in right sub tree recursively
}

So this is an extensive search and the final complexity is N where N is the number of nodes in the tree.

Adding both observations, total complexity of the algorithm is

O(h * N)

If tree is balanced, h = log N (RB tree, treap etc) If tree is unbalanced, in worse case h may be up to N

So complexity in terms of N can be given as

For balanced binary tree: O(N logN)
To be more precise, it is actual h(N + N/2 + N/4...) for balanced tree and hence should come 2hN
For unbalanced binary tree: O(N²)
To be more precise, it is actual h(N + N-1 + N-2...) for balanced tree and hence should come h x N x (N+1) / 2

So the worse case complexity is N²

Your algorithm doesn't use any memory. By using some memory to save path, you can improve your algorithm drastically.

More precisely, h(N + N/2 + N/4...) should be h * logN right? — bigpotato, Jun 25 '14 at 09:18
@bigpotato For an infinite series (N + N/2 + N/4...), the sum of terms is 2N. — Mohit Jain, Jun 25 '14 at 09:35

How to compute a least common ancestor algorithm's time complexity?

2 Answers2