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

Coding (C++)

#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

Output of coding

Table 1: Complexity Analysis Algorithm Complexity Algorithm 1 Olog n) Algorithm 2 0 (n) Table 2: Execution Time (in milliseconds) Algorithm 1 Algorithm 2 Algorithm 100 integers 200 integers 300 integers -MENU FOR PROGRAM 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 1 Enter the size of array : 100 --MENU FOR PROGRAM - 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 2 Enter number to be searched for: 22753 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 1 22753 is present in the file Enter number to be searched for: 33567 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 2 33567 is not in the file Enter number to be searched for: 5682 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 3 5602 is present in the file Enter number to be searched for: 22789 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 4 Exiting the search portal ---MENU FOR PROGRAM--- 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter number to be searched for: 5506 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 1 5586 is not in the file Enter number to be searched for: 16451 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 3 16451 is present in the file Enter number to be searched for: 5567 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 4 Exiting the search portal --MENU FOR PROGRAM- -MENU FOR PROGRAM 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 3 Values reset successful. ---MENU FOR PROGRAM--- 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 1 Enter the size of array : 300 ---MENU FOR PROGRAM---- 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 2 Enter number to be searched for: 26845 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 4 Exiting the search portal --MENU FOR PROGRAM 1. Generate Randon Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 4 Exiting the program. Goodbye... Content of 100data.txt when size is 100: 22207 17688 7917 8252 14229 2217 21823 24696 6794 3345 30586 17843 30808 30572 10326 29076 3738 26430 16476 30032 6459 6675 29431 12916 16430 29282 18894 14559 3423 26039 27217 17933 32490 5649 22930 18844 2444 6793 12887 4872 8022 15157 365 3258 3753 9292 15423 10305 19806 21643 1447 24543 1093 19159 13571 28999 28369 14115 21388 13733 25361 12948 995 15071 5602 17123 2029 538 28516 11524 22753 1921 938 23301 1439 30529 950 22840 19268 13272 15012 11924 7163 4496 27429 5209 2070 27462 8495 20723 15709 29808 19443 14881 4261 27743 13328 8790 17829 5825 Content of 100data.txt when size is 200:- 22207 17688 7917 8252 14229 2217 21823 24696 6794 3345 30586 17843 30808 30572 10326 29076 3738 26430 16476 30032 6459 6675 29431 12916 16430 29282 18894 14559 342326039 27217 17933 32490 5649 22930 18844 2444 6793 12887 4872 8022 15157 365 3258 3753 9292 15423 10305 19806 21643 1447 24543 1093 19159 13571 28999 28369 14115 21388 13733 25361 12948 995 15071 5602 17123 2029 538 28516 11524 22753 1921 938 23301 1439 30529 950 22840 19268 13272 15012 11924 7163 4496 27429 5209 2070 27462 849520723 15709 29808 19443 14881 4261 27743 13328 8790 17829 5825 8710 13664 2310 7529 18669 2119 20665 16211 18791 24696 5773 28898 24787 30242 8449 20845 6339 13793 20054 6650 2736 17818 5609 26953 3053 20646 13248 4373 21978 24370 12899 18582 32346 15589 18157 26698 21639 12996 13154 4853 30116 6227 9027 28647 11858 32765 13920 23165 31751 694 11758 10986 17085 28383 28633 31799 2791 24170 21596 5001 23465 30782 29134 19619 1352 24797 23231 12203 28640 7748 579 5169 16981 29459 14990 30061 30091 29933 449 23496 10202 25122 4356 32671 17596 31371 25045 2371 21705 24502 7583 4676 2534 16451 11151 19439 23481 21134 20643 28437 Contents of 100data.txt when size is 300:- 22207 17688 7917 8252 14229 2217 21823 24696 6794 3345 30586 17843 30808 30572 10326 29076 3738 26430 16476 30032 6459 6675 29431 12916 16430 29282 18894 14559 3423 26039 27217 17933 32490 5649 22930 18844 2444 6793 12887 4872 8022 15157 365 3258 3753 9292 15423 10305 19806 21643 1447 24543 1093 19159 13571 28999 28369 14115 21388 13733 25361 12948 995 15071 5602 17123 2029 538 28516 11524 22753 1921 938 23301 1439 30529 950 22840 19268 13272 15012 11924 7163 4496 27429 5209 2070 27462 8495 20723 15709 29808 19443 14881 4261 27743 13328 8790 17829 5825 8710 13664 2310 7529 18669 2119 20665 16211 18791 24696 5773 28898 24787 30242 8449 20845 6339 13793 20054 6650 2736 17818 5609 26953 3053 20646 13248 4373 21978 24370 12899 18582 32346 15589 18157 26698 21639 12996 13154.4853 30116 6227 9027 28647 11858 32765 13920 23165 31751 694 11758 10986 17085 28383 28633 31799 2791 24170 21596 5001 23465 30782 29134 19619 1352 24797 23231 12203 28640 7748 579 5169 16981 29459 14990 30061 30091 29933 449 23496 10202 25122 4356 32671 17596 31371 25045 2371 21705 24502 7583 4676 2534 16451 11151 19439 23481 21134 20643 28437 18528 25231 5636 22798 3426 30462 27029 31230 27877 20922 11468 30807 21282 20331 9665 11679 28695 27238 1668 24692 6523 25810 32436 24525 2295 24073 2893 25474 1909122337 30914 22031 28527 27500 19276 27541 22707 15965 385 10785 11976 26411 25896 18225 22729 23002 24140 32372 2100 5176 31887 17874 11494 4614 10945 684 25926 19544 16561 9317 16064 18495 26435 18465 23157 30884 707 18892 18992 30583 6009 26207 14748 23050 23678 21342 14261 9399 28878 28581 13437 8649 26269 29029 1776 8090 6383 13674 3897 23032 32611 5023 18726 4813 29775 23763 25306 7679 8466 26045 Table 1: Complexity Analysis Algorithm Complexity Algorithm 1 Olog n) Algorithm 2 0 (n) Table 2: Execution Time (in milliseconds) Algorithm 1 Algorithm 2 Algorithm 100 integers 200 integers 300 integers -MENU FOR PROGRAM 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 1 Enter the size of array : 100 --MENU FOR PROGRAM - 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 2 Enter number to be searched for: 22753 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 1 22753 is present in the file Enter number to be searched for: 33567 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 2 33567 is not in the file Enter number to be searched for: 5682 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 3 5602 is present in the file Enter number to be searched for: 22789 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 4 Exiting the search portal ---MENU FOR PROGRAM--- 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter number to be searched for: 5506 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 1 5586 is not in the file Enter number to be searched for: 16451 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 3 16451 is present in the file Enter number to be searched for: 5567 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 4 Exiting the search portal --MENU FOR PROGRAM- -MENU FOR PROGRAM 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 3 Values reset successful. ---MENU FOR PROGRAM--- 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 1 Enter the size of array : 300 ---MENU FOR PROGRAM---- 1. Generate Random Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 2 Enter number to be searched for: 26845 ****MENU FOR SEARCHING*** 1. Linear Search 2. Binary Search 3. Interpolation Search 4. Done with Searching Enter your choice : 4 Exiting the search portal --MENU FOR PROGRAM 1. Generate Randon Numbers 2. Search for a number 3. Reset the values of array 4. Quit from whole program Enter your choice : 4 Exiting the program. Goodbye... Content of 100data.txt when size is 100: 22207 17688 7917 8252 14229 2217 21823 24696 6794 3345 30586 17843 30808 30572 10326 29076 3738 26430 16476 30032 6459 6675 29431 12916 16430 29282 18894 14559 3423 26039 27217 17933 32490 5649 22930 18844 2444 6793 12887 4872 8022 15157 365 3258 3753 9292 15423 10305 19806 21643 1447 24543 1093 19159 13571 28999 28369 14115 21388 13733 25361 12948 995 15071 5602 17123 2029 538 28516 11524 22753 1921 938 23301 1439 30529 950 22840 19268 13272 15012 11924 7163 4496 27429 5209 2070 27462 8495 20723 15709 29808 19443 14881 4261 27743 13328 8790 17829 5825 Content of 100data.txt when size is 200:- 22207 17688 7917 8252 14229 2217 21823 24696 6794 3345 30586 17843 30808 30572 10326 29076 3738 26430 16476 30032 6459 6675 29431 12916 16430 29282 18894 14559 342326039 27217 17933 32490 5649 22930 18844 2444 6793 12887 4872 8022 15157 365 3258 3753 9292 15423 10305 19806 21643 1447 24543 1093 19159 13571 28999 28369 14115 21388 13733 25361 12948 995 15071 5602 17123 2029 538 28516 11524 22753 1921 938 23301 1439 30529 950 22840 19268 13272 15012 11924 7163 4496 27429 5209 2070 27462 849520723 15709 29808 19443 14881 4261 27743 13328 8790 17829 5825 8710 13664 2310 7529 18669 2119 20665 16211 18791 24696 5773 28898 24787 30242 8449 20845 6339 13793 20054 6650 2736 17818 5609 26953 3053 20646 13248 4373 21978 24370 12899 18582 32346 15589 18157 26698 21639 12996 13154 4853 30116 6227 9027 28647 11858 32765 13920 23165 31751 694 11758 10986 17085 28383 28633 31799 2791 24170 21596 5001 23465 30782 29134 19619 1352 24797 23231 12203 28640 7748 579 5169 16981 29459 14990 30061 30091 29933 449 23496 10202 25122 4356 32671 17596 31371 25045 2371 21705 24502 7583 4676 2534 16451 11151 19439 23481 21134 20643 28437 Contents of 100data.txt when size is 300:- 22207 17688 7917 8252 14229 2217 21823 24696 6794 3345 30586 17843 30808 30572 10326 29076 3738 26430 16476 30032 6459 6675 29431 12916 16430 29282 18894 14559 3423 26039 27217 17933 32490 5649 22930 18844 2444 6793 12887 4872 8022 15157 365 3258 3753 9292 15423 10305 19806 21643 1447 24543 1093 19159 13571 28999 28369 14115 21388 13733 25361 12948 995 15071 5602 17123 2029 538 28516 11524 22753 1921 938 23301 1439 30529 950 22840 19268 13272 15012 11924 7163 4496 27429 5209 2070 27462 8495 20723 15709 29808 19443 14881 4261 27743 13328 8790 17829 5825 8710 13664 2310 7529 18669 2119 20665 16211 18791 24696 5773 28898 24787 30242 8449 20845 6339 13793 20054 6650 2736 17818 5609 26953 3053 20646 13248 4373 21978 24370 12899 18582 32346 15589 18157 26698 21639 12996 13154.4853 30116 6227 9027 28647 11858 32765 13920 23165 31751 694 11758 10986 17085 28383 28633 31799 2791 24170 21596 5001 23465 30782 29134 19619 1352 24797 23231 12203 28640 7748 579 5169 16981 29459 14990 30061 30091 29933 449 23496 10202 25122 4356 32671 17596 31371 25045 2371 21705 24502 7583 4676 2534 16451 11151 19439 23481 21134 20643 28437 18528 25231 5636 22798 3426 30462 27029 31230 27877 20922 11468 30807 21282 20331 9665 11679 28695 27238 1668 24692 6523 25810 32436 24525 2295 24073 2893 25474 1909122337 30914 22031 28527 27500 19276 27541 22707 15965 385 10785 11976 26411 25896 18225 22729 23002 24140 32372 2100 5176 31887 17874 11494 4614 10945 684 25926 19544 16561 9317 16064 18495 26435 18465 23157 30884 707 18892 18992 30583 6009 26207 14748 23050 23678 21342 14261 9399 28878 28581 13437 8649 26269 29029 1776 8090 6383 13674 3897 23032 32611 5023 18726 4813 29775 23763 25306 7679 8466 26045