Log In
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
in Algorithms
edited by
Both take O(n)...
even the linked list ? ... should not we traverse the list to get the middle pointer ?

total recursive call will be = $O(n)$ ok !

But I think in Linked list to get to the middle we have an overhead of $O(n)$

=> $O(n\log n)$

correct if wrong
Yeah, it would take O(n) in the worst case to find the middle pointer ....
O(n logn) is right ....

but, surely we can reduce this to O(n), by just traversing from first element to  root node ....
plz explain how

1 Answer

4 votes
Best answer

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
sorry , My Editor is having some problem. brackets are not working...

@kapil ? This procedure ?

In this case recurrence relation for time complexity coming out to be :

recursive prcedure call : $T(n) = 2T\left ( \frac{n}{2} \right ) + O(1)$ => $T(n) = O(n)$

and for elements couting purpose $O(n)$ prior to the recursive call.

Total = $O(n)$

yes, this link is also saying same thing .

I read these methods from a java book earlier , which says

1). sorted list to BST ==> O(n) .

2. sorted DLL to BST ==> O(n) .

And for such questions based on trees, always apply bottom up approach along with top down approach .
Thanks !

Since we are calling the recursive function from a large span (say, start = 0 and end = n-1) and going down recursively calling itself again with smaller range. And finally if we hit a certain node in the linked list, we form a node (allocate a memory for the tree node with linked list ) for the our tree. Although we are pluging linked list nodes in the tree from list start pointer, actual recursive calls are coming from top.

I think this approach is top down. other example : f(n) = f(n-1) + f(n-2) fibonacci recursive calling from n : which is top down. Above link, and many other sources are saying it as bottom up.

Could you please refer code for the bottom up approach ?
I am aware of the difference. Just asking about your bottom up construction of tree reference/code.

Your link says it all, 

First make recursive calls until we get NULL. 

Now , start from NULL , find parent , then right child by 

parent->right = sortedListToBST(list, mid+1, end);

Hence, whole think works like left child -> parent -> right child .

I thought like this for BU .

I dont have my code as now now .

eventually constructing from bottom ! ok ! fine !, but did we gave command from bottom ? no. We gave from entire span (start =0 ,end=n-1).

In fibonacci recursive also recursion starts from N , bounce back from f(0) or f(1) only and internally added to form subsolutions f(2),f(3).etc...

That's what we call Top down, according to me.

Related questions

0 votes
1 answer
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
asked Jan 20, 2019 in Algorithms VikramRB 428 views
1 vote
0 answers
N rooms are there and they are numbered from 1 to N. A person P is in charge of room allocation and allocates these rooms inthe following way: Each query ask for two consecutive rooms. P selects two consecutive rooms out of the vacant rooms and serves the query. ... assume P selects (2,3) Seconds query onwards can not be processed. because although 1,4 are vacant, these rooms are not consecutive.
asked Aug 23, 2016 in Unknown Category dd 303 views
0 votes
0 answers
A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence ... can be calculated as the column number of the element we are looking for summing with the $row \times column$ number of elements. How does the above recurrence relation work?
asked Jan 7, 2019 in DS kauray 216 views
0 votes
1 answer
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked Jan 4, 2019 in Algorithms Mayankprakash 419 views