Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 238
bigpotato Avatar asked Mar 20 '23 09:03

bigpotato


1 Answers

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)).

like image 80
0x90 Avatar answered Mar 29 '23 23:03

0x90