CODEWITHSUNDEEP
calgorithmsortingtime-complexitybinary-search-tree
user3289840
user3289840

Reputation: 251

What time complexity has a function that sorts an array of struct using a BST?

I have a function that sorts an array using a BST. First I create the tree using for loop and function insert (that insert data in the tree keep ordered) and then I visit in-order the tree and copy each node in sort mode in a new temporary archive. Here is my code:

double btree_sort(SPerson Archive[], unsigned int ne, double    *btree_creating_time)
{
int i = 0;
TBinaryTree BinaryTree = NULL;

cont = 0;

LARGE_INTEGER freq;
LARGE_INTEGER t0, tF, tDiff;

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&t0);
/*Algorithm*/
for (i = 0; i < ne; i++)       /*Creating B-Tree*/
    BinaryTree = binarytree_insert(BinaryTree, Archive[i]);
QueryPerformanceCounter(&tF);
tDiff.QuadPart = tF.QuadPart - t0.QuadPart;
*btree_creating_time = tDiff.QuadPart / (double)freq.QuadPart;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&t0);
inorder(BinaryTree, Archive);
/*end*/
QueryPerformanceCounter(&tF);
tDiff.QuadPart = tF.QuadPart - t0.QuadPart;

free(BinaryTree);
return tDiff.QuadPart / (double)freq.QuadPart;
}

int  inorder(TBinaryTree BinaryTree, SPerson Archive[])
{
if (BinaryTree)
{
    inorder(BinaryTree->left,Archive);  

    swap(&Archive[cont++], &BinaryTree->information);

    inorder(BinaryTree->right, Archive);

}                  
return 1;
}

 TBinaryTree binarytree_insert(TBinaryTree bt, SPerson to_add)
{
if (bt == NULL)   
{
    TNode *new_node = create_node(to_add);
    if (new_node == NULL) 
    {
        MessageBoxA(0, "Error allocating memory.", "", 0);
        exit(1);
    }
    return new_node;
}
else
{
    if (strcmp(to_add.id, bt->information.id)<0)
    {
        bt->left = binarytree_insert(bt->left, to_add);
        return bt;    
    }
    else
    {
        bt->right = binarytree_insert(bt->right, to_add);
        return bt;  
    }
}
}

Consider that:

  1. inserting a b-tree has time complexity of Θ(1) in best case and Θ(nlogn) in worst. (Anyway is right to write Θ or i should say O to best case and Ω to worst ?)

  2. in-order vist has time complexity of Θ(n)

So inserting n elements in the tree ,visits, and swapping have a time complexity of:

Best case: [only one elemenst] Θ(1) + [Θ(1) + Θ(4)] [swap function time complexity]

Worst case: Θ(nlogn) + [Θ(n) + Θ(4)]

Am I right? Any advice? Thanks in advance.

Upvotes: 1

Views: 125

Answers (2)

Anand Kumar
Anand Kumar

Reputation: 9

Insert operation on a binary search tree has worst case time complexity of O(logn). Inserting n numbers would be O(nlogn). Followed by inorder traversal of all n nodes which is O(n). Thus O(nlogn) + O(n) which is O(nlogn).

Upvotes: 1

nidhimj22
nidhimj22

Reputation: 445

Worst case complexity are called O - Big Oh notation. We usually only use the worst case complexity. Also insertion of all nodes in a Btree is O(nlogn). So sorting a tree is inserting all the keys and then traversing the tree in inorder which has the complexity of O(n).

So the overall complexity is O(nlogn) + O(n) which is O(nlogn)

Upvotes: 5

Related Questions