4
$\begingroup$

Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height?

My idea: the height of an AVL tree is originally $O(\log(n))$ where $n$ is the number of elements. After insertion of $n^2$ elements, its height will be:$$O(\log(n+n^2))=O(\log(n^2))=O(2\log(n))=O(\log(n))$$

My answer would be $O(\log(n))$ but I'm having doubts.

Why is the asymptotic complexity of the result the same despite the fact that there are more elements?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by $N^2$ entries? Do you mean $N^2$ new items are inserted or that total items are $N^2$. Based on your argument, I assume it is the former. $\endgroup$ – Paresh Nov 28 '12 at 15:58
  • $\begingroup$ I mean after the insertion of $N^2$ new elements $\endgroup$ – abc Nov 28 '12 at 15:59
  • 1
    $\begingroup$ I see. In either case, your answer looks valid to me, and the working more or less all right. That is, if you are only interested in the asymptotic bounds, and not actual upper limits. $\endgroup$ – Paresh Nov 28 '12 at 16:10
1
$\begingroup$

To show that this isn't always the case, imagine you added $e^n$ elements, then it would take

$$O(\log(n+e^n))=O(\log(e^n))=O(n)$$

But what does that really mean? It's not that your binary tree takes $O(n)$ time on $n$ elements to find something. Rather, it takes $O(\log(m))$ time for $m=n+e^n$ elements.

I can understand why you would be confused; if you had to search linearly through a list, and then you added $n^2$ elements, it would take $O(n^2$) time in terms of the original input, but not the new input, for which it would take $O(m)$ time on $m=n+n^2$ elements.

Chances are you didn't want to solve for the asymptotic solution; it generally doesn't make sense to. What you probably want is the approximation $\log(n+n^2)\approx\log(n^2)=2\log(n)$; that is,

For a self-balancing tree, squaring the input size doubles the search time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.