You are given a startup C++ code with the main function. You are required to implement the two recursive algorithms (call the function to implement the divide and conquer algorithm as: DivideByHalf and the function to implement the decrease by one algorithm as: DecreaseByOne). The way the code will be executed starting with asking the user for the array size, max value for an element in the array and an option (1 or 2). The code will run for 1000 trials and compute the average time of one of the two algorithm implementations depending on the value entered for option. You will run the code for array size values of 1000, 10000 and 100000 for max value of 50000 in each case for each of the two options 1 and 2. The timers are setup to determine the running time in nanoseconds.For each trial, the array (of a specific array size) will be filled with random integers from 1 to 50000. Tabulate the results for the running time of the two recursive algorithms for the above three values of array size and analyze the results. You should compare/explain the performance of the two algorithms and interpret the reasons for the difference or similarity in their performance, depending on the case. Also, come up with a recurrence relation for the number of times the basic operation is executed in the Decrease by One algorithm, and solve the recurrence relation to evaluate the theoretical time complexity. Show all the work.

#include #include #include #include

#include #include #include

using namespace std;

// Implement here the DivideByHalf algorithm

// Implement here the DecreaseByOne algorithm

int main(){

using namespace std::chrono; srand(time(NULL)); int arraySize; cout << "Enter an array size: "; cin >> arraySize; int maxValue; cout << "Enter max. value: "; cin >> maxValue; int option; cout << "Enter 1 for dividing the array size by half; 2 for decreasing the array size by 1" << endl; cin >> option; double totalTime_nano = 0; int numTrials = 1000; for (int trials = 1; trials <= numTrials; trials++){ int *arrayPtr = new int[arraySize]; for (int index = 0; index < arraySize; index++) arrayPtr[index] = 1 + ( rand() % maxValue); int minValue = -1; if (option == 1){ high_resolution_clock::time_point t1 = high_resolution_clock::now(); int minIndex = DivideByHalf(arrayPtr, 0, arraySize-1); minValue = arrayPtr[minIndex];

high_resolution_clock::time_point t2 = high_resolution_clock::now(); duration time_nano = t2 - t1; totalTime_nano += time_nano.count(); } else if (option == 2){ high_resolution_clock::time_point t1 = high_resolution_clock::now();

minValue = DecreaseByOne(arrayPtr, arraySize);

high_resolution_clock::time_point t2 = high_resolution_clock::now(); duration time_nano = t2 - t1; totalTime_nano += time_nano.count(); } else{ cout << "Invalid option " ; return 0; }

//cout << "Min. element is: " << minValue << endl;

delete[] arrayPtr; }// trials loop

cout << "Option " << option << " : Average time " << (totalTime_nano/numTrials) << " nano seconds " << endl;

system("pause");

return 0; }