Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
1  
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. – Paresh Nov 28 '12 at 15:58
I mean after the insertion of $N^2$ new elements – newbie Nov 28 '12 at 15:59
1  
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. – Paresh Nov 28 '12 at 16:10

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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