CODEWITHSUNDEEP
data-structuresbig-otime-complexitybinary-search-tree
user3575020
user3575020

Reputation: 137

Time complexity of creating a BST with minimal height given a sorted array with elements in increasing order

I tried to solve this problem in 2 ways. The most obvious solution is to use the standard insert operation of BST starting with the root node and recursively proceed further. However, to insert each node it will take me log N time. Since I have to do it for N nodes, it will take me totally NlogN. So I thought about how to cut off few calls so that I do not need to go through the entire tree for inserting each node. In this approach, after inserting the root I only pass the half of the array(left-half) to generate left subtree and right half of the array(right-half) to generate the right subtree. The code for it is as follows:

public static TreeNode createMinBST(int arr[], int start, int end){
 if (end < start) {
 return null;
 }
 int mid = (start + end) / 2;
 TreeNode n = new TreeNode(arr[mid]);
 n.left = createMinBST(arr, start, mid - 1);
 n.right = createMinBST(arr, mid + 1, end);
 return n;
 }

This, I was able to come up easily. But I am finding it difficult to analyse the runtime of this code. Any help please? Could you throw some light on how to arrive at the runtime too, so that I can reuse that analysis for other problems?

Upvotes: 4

Views: 1921

Answers (2)

Patrick87
Patrick87

Reputation: 28302

Let T(n) be the time that createMinBST takes on an input of size n = end - start. We can write a recurrence relation for T(n) as follows:

T(0) = a
T(n) <= 2T(floor(n/2)) + b

Note that I write <= on purpose; we will have equality only when both recursive calls have the same size, which will only occur if the overall size is odd. For this to work all the way down the recursion tree, you'd be restricted to initial sizes of the form S = 1, 3, 7, ..., S(n-1)*2 + 1, .... However, we are free to assume this input size as it is worst-case (passing fewer than half the elements to one of the recursive calls is no worse than passing the same to both).

There are several ways we can figure out the solution here. We can write out some terms, make a guess and prove it by induction. Here are a few terms:

T(0) = a
T(1) <= 2T(0) + b = 2a + b                 = 2a + b
T(2) <= 2T(1) + b = 4a + 2b + b            = 4a + 3b
T(4) <= 2T(2) + b = 8a + 4b + 2b + b       = 8a + 7b
T(8) <= 2T(4) + b = 16a + 8b + 4b + 2b + b = 16a + 17b
...
T(n) <= (2n)a + (2n-1)b = 2(a+b)n - b

I leave as an exercise to show that this solution holds true for all n. Of course, an asymptotic bound for this is O(n).

You can also use the "Master Method" once you have a nice recurrence relation as above.

Coming up with the recurrence relation is done as follows:

  1. Identify the base case(s), and the fixed values of T(n) for these.
  2. For recursive cases, find the number of recursive calls and the problem size for each.

When analyzing a recurrence relation, identify the worst-case (if that's the bound you're interested in) and make sure your relation is correct for the case. Then, use any method for resolving recurrence relations you like. If you want to list terms, guess and then prove the solution, choose values that are easy to compute with; in my case, powers of two worked, but other recurrence relations might have different patterns (in fact, here, we could have used a more exact equation and chosen true-worst-case inputs of 1, 3, 7, 15, ...).

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372784

This algorithm runs in time O(n). Here are two ways to see this.

First, you can note that each call to the function runs in time O(1) and that each call "uses up" one of the nodes. This means that there can only be O(n) total calls, so the total work will be O(n).

Alternatively, you can use the Master Theorem. Your function does O(1) work and makes two calls on subarrays of size (roughly) n / 2, so you get the recurrence

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

By the Master Theorem, this solves to O(n).

Hope this helps!

Upvotes: 2

Related Questions