CODEWITHSUNDEEP
algorithmdata-structurestreebinary-search-tree
Nishant Kumar
Nishant Kumar

Reputation: 6083

Sorting By:Binary Search Tree

I am little bit confused regarding worst Case time and Avg case Time complexity. My source of confusion is Here

My aim is to short data in increasing Order: I choose BST to acomplish my task of sorting.Here I am putting what I am doing for printing data in Increasing order.

 1) Construct a binary search tree for given input.
        Time complexity: Avg Case O(log n)
                         Worst Case O(H) {H is height of tree, here we can Assume Height is equal to number of node H = n}

 2)After Finishing first work I am traversing BST in Inorder to print data in Increasing order. 
        Time complexity: O(n) {n is the number of nodes in tree}

Now  I analyzed total complexity for get my desire result (data in increasing order) is for Avg Case: T(n) = O(log n) +O(n) = max(log n, n) = O(n)
      For Worst Case : T(n) = O(n) +O(n) = max(n, n) = O(n)

Above point was my understanding which is Differ from Above Link concept. I know I am doing some wrong interpratation Please correct me. I would appreciate your suggestion and thought.

Please Refer this title Under Slide which I have mentined: enter image description here

Upvotes: 1

Views: 2402

Answers (2)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

The time complexity needed to construct the binary tree is n times the complexity you suggest as you need to insert each node.

Upvotes: 1

Stefan Haustein
Stefan Haustein

Reputation: 18793

In (1) you provide the time per element, you need to multiply with the # of elements.

Upvotes: 1

Related Questions