Computational Complexity

Question:

Discuss an algorithm that you have developed and include a discussion on its computational complexity.

Summary:

An Algorithm to create a binary search tree from any sorted array and to find its time complexity.

Explanation:

Binary search tree:

A binary search tree is a sorted binary tree in which the value of the left subtree is less than the root node for each node. The value in the right subtree is larger than the root node. We can perform three operations:

1) Search– Searching the element of a particular location in a binary search tree.

2) Insert– Inserting a new node/value to the binary search tree.

3) Delete– Deleting a particular node in the binary tree.

 

The computation complexities of the binary search tree will be,

Operations	Time complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

Binary search tree provides good logarithmic time performance in the best and average cases.

In a sorted array, the middle element is the root node of the array. For example, let us consider an array Arr with certain values:

Arr[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}

In the tree below, all the left subtree nodes contain the smaller value, and the right subtree contains greater values than the root node 7.

Algorithm of binary search tree:

Start

Recursive function Insert.

if size>=0, return NULL.

set mid=size/2 and root=arr[mid].

Define two subarrays L[mid], R[mid].

Divide the array into two arrays, L[mid] will have values from 0 to mid and R[mid] will have values from mid+1 to size index.

Insert for array L and hold value for root->left.

Insert for array R and hold value for root->right.

End

Source code:

#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node*left,*right;
};
// a utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->key=item;
temp->left=temp->right=NULL;
return temp;
}
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\n",root->key);
inorder(root->right);
}
}
struct node *insert(struct node*node, int key)
{
if(node==NULL)
return newNode(key);
if(key<node->key)
node->left=insert(node->left,key);
else if(key>node->key)
node->right=insert(node->right,key);
return node;
}
int main()
{
struct node*root=NULL;
root=insert(root, 7);
insert(root,1);
insert(root,8);
insert(root,3);
insert(root,9);
insert(root,5);
insert(root,2);
insert(root,4);
insert(root,12);
insert(root,10);
insert(root,11);
insert(root,13);
insert(root,6);
insert(root,0);
inorder(root);
return 0;
}

 

OUTPUT:

 

The time complexity of this algorithm will be:

Total work done will be: cn+cn+cn+…+cn

The height of the binary search tree is logn.

So, the computational complexity of this algorithm will be O(nlogn).

 

Also, read Write a python code that fulfills the following requirements.