The Gateway to Computer Science Excellence
+3 votes
602 views
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 by Veteran (57.2k points)
edited by | 602 views
0
Both take O(n)...
0
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
+1
Yeah, it would take O(n) in the worst case to find the middle pointer ....
–1
O(n logn) is right ....

but, surely we can reduce this to O(n), by just traversing from first element to  root node ....
0
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) .

by Veteran (50.9k points)
selected by
0
sorry , My Editor is having some problem. brackets are not working...
+1

@kapil ? This procedure ? http://articles.leetcode.com/convert-sorted-list-to-balanced-binary

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)$

+1
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 .
0
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 node.data ) 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 ?
+1
0
I am aware of the difference. Just asking about your bottom up construction of tree reference/code.
0

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 .

0
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
198,314 comments
105,011 users