ME test

Question

Consider a function AVLConstruction(). Which takes an array n elements as input in Ascending order and produce output as AVL tree for given array. AVLConstruction() function selects the median of the array and put it as the Root element. Recursively build Left subtree from the left half of array and right half of the array. what will be the complexity of AVLConstruction()?

A) O(nlogn)

B) O(n2)

C) O(n3)

D) O(n)

Answer 1

According to the problem description ,

We need to find the median so we know if :

Time needed to find median  = O(n) using selection algorithm

Now for recursive parts we are considering the left and right subtrees and these are of almost same sizes.

Hence if T(n) is complexity of entire problem so for subproblems we need 2T(n/2) time..And O(n) for median finding as mentioned earlier..Hence recurrence relation for time T(n) will be :

           T(n) = 2T(n/2) + O(n) 

==>     T(n) = O(nlogn)    by Masters theorem

Hence correct answer is O(nlogn)

Comments

@Habib as input is already given in ascending order should not the finding median take O(1) time?

---

@ Habib input array is sorted for median it will take o(1) time why you are taking o(n).?

---

Wonderful explanation Habib, but array is sorted and so median can be found in O(1) time. Please edit your solution.