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?

Answer 1

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