# What is the time complexity of this program?

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);
}

• @gnat, 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 in my opinion should be working in O(nlogn) by the master method? – Dhruv Mullick Jul 23 '15 at 21:55
• Could they have mentioned that complexity keeping the worst case in mind? Normally when you see quicksort, for example, they mention that O(nlogn) is the average case complexity - and it would be O(n^2) in worst case. – Mehdi Maujood Jul 23 '15 at 22:40
• O(n log n) is in O(n^2), so I don't see any contradiction here. (Note: I haven't checked the math, to verify that the algorithm actually is in O(n log n), but even assuming that it is, it is still also on O(n^2).) – Jörg W Mittag Jul 23 '15 at 22:42

• @DhruvMullick ask them if they want worst case O(n log n), or if they'd be happy with average O(n log n) / worst-case O(n^2). The latter describes quicksort, for example, which people tend to think of as suitable for general use. – AakashM Jul 24 '15 at 13:26