Big O Running Time for different Data Strucutres

I've tried to come up with the Big O Running time of the following data structures. Are they Correct?

• Inserting n integers into an initially empty AVL Tree (best case) O(log n)

• Inserting n integers into an initially empty AVL Tree (worst case) O(log n)

• Inserting n i开发者_开发知识库ntegers into an initially empty binary search tree that does not enforce structure properties (best case) O(log n)

• Inserting n integers into an initially empty binary search tree that does not enforce structure properties (worst case) O(n)

Also an explanation as to why they are incorrect would be helpful

I am assuming here you need the total time for inserting all the elements:

(1) at best case for an AVL tree, you will never need to go below the root, [i.e. all the elements are equal to the root] so it will be O(n). [never need to deepen more then 1 step, regardless of the tree's size]. O(1) per element.

(2) worst case for AVL tree: inserting n integers to an AVL tree is O(nlogn). each step is O(log(T)) where T is the size at that moment. O(log1) + O (log2) + ... + O(logn) = O(log1 + log2 + ... + logn) = O(log(1*...*n)) = O(nlogn). so O(nlogn). O(logn) per element

(3) with no structure enforce, best case, still O(n), same reason for (1). at best case, all elements you add are exactly the root, so you will never need to go down in the tree, no matter what its size is. O(1) per element.

(4) with no structure enforce, worst case: as said in other answers, finding the place for each element is O(n), so at overall you will have a worst time complexity of O(n^2). O(n) per element.

This is incorrect in your definition:

Inserting n integers into an initially empty AVL Tree (best case) O(log n)

You can't access (and copy) n data items in less than n operations, because you should read each item (so, O(n) is bare minimum of moving on n elements).

So, my assumtion is that you give correct O() for single element (this is a bit wrong, because best can be achieved on special inputs; your estimations are of average case, not the best), so, for total described operation I'll multiply each with O(n):

• Inserting n integers into an initially empty AVL Tree (best case) O(n*log n) UPDATE: this is the average; best time can be lower on special inputs.

• Inserting n integers into an initially empty AVL Tree (worst case) O(n*log n)

• Inserting n integers into an initially empty binary search tree that does not enforce structure properties (best case) O(n*log n) UPDATE: this may depend on implementation and on sequence of integers; so best case is O(n) (see comments).

• Inserting n integers into an initially empty binary search tree that does not enforce structure properties (worst case) O(n*n)

How can inserting n integers result in a Big O of O(logn). That doesn't make any sense. Surely reading the integers itself would take at least O(n).

So for the unbalanced, BST example the worst case is where you insert a sorted list of numbers like 1,2,3,4. Inserting 1 takes 0 time. Inserting 2 takes ~1 time. Inserting 3 takes ~2 time. etc. This amounts to 1+2+3+...+n = O(n^2).

Similarly in the best case scenario, each subsequent insert takes log(i) time. So the total running time is log(1)+log(2)+log(3)+...+log(n). What this evaluates to is not immediately obvious. But if you know a bit of calculus, you can see that this is (almost) the trapezoidal rule approximation to integral of log n from 1 to n. This is approximately nlogn - n = O(nlogn).

I'm sure you can do similar analysis for the AVL trees.

I'm sorry, but they are all wrong.

what you used are the Big-Os for a single insertion. If you do n of them, you have to take that times n.

So the correct figures are:

Inserting n integers into:

• AVL Tree (worst case): O(log(n) * n)
• AVL Tree (best case): This is difficult, but I guess it's O(log(n) * n), too
• binary search tree that does not enforce structure properties (best case): O(n) - The best case insertion time for 1 item is actually O(1)
• binary search tree that does not enforce structure properties (worst case): O(n^2) - if you do not enforce structure properties, you might end up with a completely unbalanced tree, so in the worst case your tree of n elements has a height of n => Your tree will deform into a list.

Yes, you're correct, if you multiply everything with n. Your running time is for one element.