What is the time complexity of this program?

Question

An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal.

They say that the time complexity for the following code is O(n^2). But in my opinion it should be O(nlogn). I'm confident about calculating O() for most algorithms, but here there's a divide and conquer algorithm, which runs as T(n) = T(n/2) + O(n), which I believe should be working in O(nlogn) by the master method?

Can someone please tell how the complexity is O(n^2)?

The idea of the code is :

The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1′ and ‘n-1′ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.

For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40.

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

// A utility function to create a node
struct node* newNode (int data)
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// A recursive function to construct Full from pre[]. preIndex is used
// to keep track of index in pre[].
struct node* constructTreeUtil (int pre[], int* preIndex,
                            int low, int high, int size)
{
    // Base case
    if (*preIndex >= size || low > high)
        return NULL;

    // The first node in preorder traversal is root. So take the node at
    // preIndex from p re[] and make it root, and increment preIndex
    struct node* root = newNode ( pre[*preIndex] );
    *preIndex = *preIndex + 1;

        // If the current subarry has only one element, no need to recur
    if (low == high)
        return root;

    // Search for the first element greater than root
    int i;
    for ( i = low; i <= high; ++i )
        if ( pre[ i ] > root->data )
            break;

    // Use the index of element found in postorder to divide postorder array in
    // two parts. Left subtree and right subtree
    root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
    root->right = constructTreeUtil ( pre, preIndex, i, high, size );

    return root;
}

// The main function to construct BST from given preorder traversal.
// This function mainly uses constructTreeUtil()
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}

Answer 1

While the stated algorithm is O(n log n) on the average case, it is O(n^2) in the worst case, i.e. when used to reconstruct a tree in which each node has an empty branch either to its left or right. Such a tree has a depth of n, and therefore the algorithm will recurse n times, each recursion requiring an average of n/2 comparisons to complete.