Recurrence relation in constructing balanced tree from linked list and array

Question

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

Comments

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

Answer 1

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

Comments

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.