Let S be a sorted array of n integers Give an algorithm that

Let S be a sorted array of n integers. Give an algorithm that constructs a BST of depth O(log n) that stores the elements of the S. Analyze the worst-case run time of your algorithm. Your grade depends on the run time.

Solution

So, we have a sorted array S and we need to create a BST; the height of which is of O(log n).

In order to fulfill our requirement, if we observe here the given array is in sorted order this means that in order travarsal of a binary search tree is given, and in order to make sure that the depth of the treaa must be always O(log n), we need to create a Balanced binary seacrh tree. The algorithm for which is given below.

Algorithm for creating a balanced binary search tree from a sorted array:

This task will take O(n) time is worst case, because when you start selecting the root one by one then you go to left subtree as well as the light subtree it means that every element needs to be accessed once. If we calculate the recurrence relation of the algorithm then it would be T(n)=2T(n/2)+c

after calculating time complexity using master theorem this will fall under Case 1 of the master theorem and the complexity will be T(n)=O(n).