CODEWITHSUNDEEP
data-structuresbinary-tree
sam2015
sam2015

Reputation: 113

BinaryTree inOrder Traversal Sorting complexity

I am confused to why quicksort, shellsort, mergesort...all O(nlog(n)) algorithms repeatedly mentioned as popular sorting algorithms, Doesn't inorder traversal of a binarysearch tree give O(n) complexity to sort a tree? What am I missing?

Upvotes: 1

Views: 744

Answers (3)

Subhankar
Subhankar

Reputation: 1

Any traversals of a binary tree is O(n). But that is not sorting. Having a BST meaning that is already a sorted tree. You are just traversing it. Building a BST is the sorting process which is asymptotically O(nlog(n)). Please note O(n) + O(nlog(n)) is same as O(nlog(n)).

Upvotes: 0

Al Ameen
Al Ameen

Reputation: 372

Basically there are 6 types of complexity. O(1),O(logn),O(n),O(nlogn),O(n^2),O(n^3).

For first part of your question why popular sorting algorithm are having O(nlogn) complexity its simply because we cannot sort an array in O(n) complexity. Its because for O(n) complexity you want to sort the array in only one loop. That is not possible since we cannot sort an array in one strech.

So the next possible complexity is O(nlogn). That is dividing and conquer method for example in merge sort We find the middle element sort each side of that recursively. for recursion since it decreasing size to half each time the complexity is o(logn). For sorting part it make the complexity to O(nlogn).

For Next part of your question remember the fact that all basic operation like insertion,deletion in a BST is having the complexity of O(logn) where logn is the height of the tree.

So if you sort a tree using o(n) complexity that make it O(nlogn) in total.

Comment me if you didnt got my point. This is the simple way to answer it i think.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490058

No. Building the tree has O(N log N) complexity (i.e., you're inserting N items into the tree, and each insertion has logarithmic complexity).

Once you have the tree built, you can traverse it with linear complexity (especially if it's a threaded tree), but that's not equivalent to sorting--it's equivalent to traversing an array after you've sorted it.

Although they have the same asymptotic complexity, building a tree will usually be slower by a substantial factor, because you have to allocate nodes for the tree and traverse non-contiguously allocated nodes to walk the tree.

Upvotes: 2

Related Questions