Skip to main content
Deleted incorrect claim.
Source Link
quicksort
  • 4.3k
  • 1
  • 10
  • 21

We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|S|$$|\bar{S}|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.

If $a$ and $b$ are passed as pointers, this is actually $O(1)$ time.

We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|S|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.

If $a$ and $b$ are passed as pointers, this is actually $O(1)$ time.

We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|\bar{S}|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.

Source Link
quicksort
  • 4.3k
  • 1
  • 10
  • 21

We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|S|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.

If $a$ and $b$ are passed as pointers, this is actually $O(1)$ time.