I am doing the program to construct a BST from given preorder traversal. I thought about a recursive logic, which is the naive method to solve this problem. For the preorder, the root will always be the first node in the traversal. And the point at which values start getting greater than the root denotes the right subtree, similarly values less than root indicate that they exist in left subtree. Since it's not necessary that the nodes in both subtrees are half of total nodes, the recurrence relation becomes somewhat like this :
T(n) = T(k) + T(n-k) + c [constant work done for each recursive call] assuming k nodes in left/right subtree and n-k in the other.
Similar approach is expressed in method 1 of this post : http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
The time complexity of the method is given as O(n^2), which is what confuses me, as I am unable to solve the above recurrence relation wherein the number of nodes in each subtree may vary, or maybe the recurrence formulated is incorrect.
I'd appreciate any guidance on this, I've looked up master theorem, and other similar questions here to get time complexity for recurrence problems, but still unable to solve above one. Thanks.
T(n) = T(k) + T(n-k) + c describes an O(n) solution. And the optimal solution to your problem is indeed O(n). The second algorithm described in the post http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/ is an example of solving this problem in O(n).
The O(n^2) complexity is for the first algorithm described in the post you included. In that algorithm, there's an O(n) step for each node to determine the partition between the left and right subtree:
Pay attention to the following lines:
...
for ( i = low; i <= high; ++i )
if ( pre[ i ] > root->data )
break;
...
So in this version, the algorithms should be described as T(n) = T(k) + T(n-k) + c + n, which describes an O(n^2) algorithm.