recategorized by
2,713 views
3 votes
3 votes
Consider the following algorithm to build a balanced search tree from a sorted sequence.

* Make the mid-point of the sequence the root of the tree

* Recursively construct balanced search trees from elements to the left and right of the midpoint and make these the left and right subtrees of the root.

A. What is the complexity of this procedure where the sorted sequence is a sorted list?

1- O(n)
2- O(n log n)
3- O(n2)
4- Depends on the contents of the original sequence.
B. What is the complexity of this procedure where the sorted sequence is a sorted array?

1- O(n)
2- O(n log n)
3- O(n2)
4- Depends on the contents of the original sequence
recategorized by

1 Answer

Best answer
4 votes
4 votes

A). If we see the first basic approach , then we can find the middle element in O(n) .

We are using here top - down approach i.e , Recursively designing BST from root to leaves  .

List middle element can be found in O(n) which is the root .

Then, similarly , left subtree and right subtree mid element (root) can be found in O(n) time .

root cost = n 

Left + right subtree cost = 2n 

........................

Total cost = n + 2n + 4n + 8n + ..........  = O(n)

and the height is O(h) = O(log n)

Hence, total complexity ==> O(n logn) .

Now, we use 2nd approach , which can reduce this complexity to O(n) .

Apply both top down and bottom up approach,

First finding middle element takes O(n) time .

Now, traverse along first element to root which has n/2 elements in the path as the tree is balanced , which takes O(n). This follows bottom up approach .

And, similarly, making root element as head pointer , make a BST (right subtree ) just by traversing the elements. This follows top down approach .

Hence , total time ==> O(n + n + n) = O(n) . This includes finding the mid element and traversing from leaf to root and then traverse from root to leaf .

B). Simple procedure , access all the elements in O(n) .

selected by

Related questions

1 votes
1 votes
1 answer
2
5 votes
5 votes
1 answer
4
hacker16 asked Nov 14, 2017
3,424 views
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?O(n)O(1)θ(n2)θ...