discuss the complexity of all searching algorithms that implemented in below coding.

Coding : #include #include #include #include using namespace std;

//Function definitions for all algorithms

//generate and write random numbers to a file void generateWrite(int array[], int size){ //create a write stream object ofstream fout("100data.txt");

//If file cannot be created then return if(!fout){ cout

//seed random number generator srand(191020880);

for(int i=0; i

//write to the file fout

//close the file object fout.close(); }

//linear search int linearSearch(int arr[], int n, int x) { int i; for (i = 0; i

//binary search: a recursive binary search function. //It returns location of x in given array if present, // otherwise -1 int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then move to left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here if the element is not present in array return -1; }

//Read numbers from a text file void readNumbers(int array[], int size){ //open the file ifstream fin; fin.open("100data.txt");

//check for opening error if(!fin){ cout

//loop counter int count = 0;

//read numbers into the array while(fin >> array[count]){ count++; }

//close the file fin.close(); }

//Interpolation search: if x is present in arr[0..n-1], then returns // index of it, else returns -1. int interpolationSearch(int arr[], int lo, int hi, int x) { int pos; // Since array is sorted, an element present // in array must be in range defined by corner if (lo = arr[lo] && x x) return interpolationSearch(arr, lo, pos - 1, x); } return -1; //if not present }

//Driver program int main(){ //declare the array with max size as 300 int rnums[300];

//loop choice variable int ch;

do{ //Menu for the program cout>ch;

//Proceed as per the input received //and call appropriate methods switch(ch){ //write random values to the file case 1: cout>size; generateWrite(rnums, size); break; case 2: //Search for an integer //first read the numbers from the file readNumbers(rnums, size);

//The array needs to be sorted before searching sort(rnums, rnums+size);

//variable to store presence of element //-1 if not present, else its index value int ele;

int ch2; //loop variable do{ cout>search;

//Menu for Searching algorithms cout>ch2;

//proceed as input received //and call appropriate methods switch(ch2){ case 1: //call and store the position of 'search //if -1, it means element not present ele = linearSearch(rnums, size, search); if(ele == -1){ cout

break; case 3: //Reset the array for(int i=0; i

cout Algorithm Complexity Table 1: Complexity Analysis Algorithm 1 Algorithm 2 Odlog n) O(n) Table 2: Execution Time (in milliseconds) Algorithm 1 Algorithm 2 Algorithm 100 integers 200 integers 300 integers