URGENT PLEASE! So I have this question for Data structure and algorithm.

In this assignment, you need to calculate the asymptotic running time of 10 functions in this file:

insert, insertionSort, remove, indexOf_iter, selectionSort, binSearches, rmzeroes, keepDoubling, partition, merge

Most of the functions are useful. A few are not very useful. If you want to see what they do, you can use my print_array function to take a look. But it is not necessary to understand what they do in order to complete this assignment.

For each function, calculate its running time mathematically. Then test your calculation experimentally by running the doubling test. The main program in this file performs the doubling test.

All you need to submit is a list of each function name with its running time. I won't check your mathematical calculation or your doubling test, unless you ask. But doing these activities is key to understanding

And here is the code:

#include #include #include #include using namespace std; using namespace std::chrono;

// In case you want to check what the function is doing void print_array(int A[], int n) { for (int i=0; i

// Inserts an integer into a sorted array of integers void insert(int A[], int n, int num) { int i; for (i=0; i

// Sorts an array void insertionSort(int A[], int n) { for (int i=0; i

// Removes an integer from a sorted array of integers int remove(int A[], int n, int num) { int i; for (i=0; i num) return n; for (i++; i

// Finds index where key occurs in a sorted array, or returns -1 if not there int indexOf_iter(int a[], int lo, int hi, int key) { while (lo <= hi) { int mid = (lo + hi) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else return mid; } return -1; }

// Sorts an array of integers void selectionSort(int A[], int n) { for (int j=n-1; j>0; j--) { int m = 0; for (int i=0; i<=j; i++) if (A[m] < A[i]) m = i; if (m != j) { int temp = A[m]; A[m] = A[j]; A[j] = temp; } } }

// Searches for all the elements in a sorted array, one by one // If it ever doesn't find one, it returns a message // Of course it finds them all, because it searches for things that are there // So this function is worthless void binSearches(int A[], int n) { int count = 0; for (int i=0; i 0) cout << "That is weird " << endl; }

// Removes all the zeroes from a sorted array // In a slow way int rmzeroes(int A[], int n) { for (int i=n; i>=0; i--) { if (indexOf_iter(A,0,n-1,0) == -1) return n; n = remove(A,n,0); } return n; }

// Continually doubles the first element of an array // After each time it resorts the array void keepDoubling(int A[], int n) { for (int i=0; i

// Partitions array around the first element // Smaller elements to the left // Larger elements to the right void partition(int A[], int n) { int p = A[0]; int lo = 0, hi = n-1; while (lo < hi) { while (A[lo+1] <= p) { A[lo] = A[lo+1]; lo++; } while (A[hi] > p) { hi--; } if (lo+1 < hi) { A[lo] = A[hi]; A[hi] = A[lo+1]; lo++; hi--; } } A[lo] = p; }

// Merges two sorted arrays into one sorted array void merge (int A[], int B[], int C[], int n) { int i=0, j=0, k=0; while (i

float run_function(string funcname, int num_num) { auto start = high_resolution_clock::now(); auto stop = high_resolution_clock::now();

unsigned seed = system_clock::now().time_since_epoch().count(); uniform_int_distribution u(0,100); //uniform_int_distribution u(0, INT_MAX-1); default_random_engine e(seed); // generates unsigned random integers

int *A = new int[num_num]; for (int i=0; i

if (funcname == "insert") { int x = u(e); sort(A,A+num_num); start = high_resolution_clock::now(); insert(A,num_num,x); stop = high_resolution_clock::now(); } else if (funcname == "insertionSort") { start = high_resolution_clock::now(); insertionSort(A,num_num); stop = high_resolution_clock::now(); } else if (funcname == "remove") { int x = A[0]; sort(A,A+num_num); start = high_resolution_clock::now(); remove(A,num_num,x); stop = high_resolution_clock::now(); } else if (funcname == "indexOf_iter") { int x = u(e); sort(A,A+num_num); start = high_resolution_clock::now(); indexOf_iter(A,0,num_num-1,x); stop = high_resolution_clock::now(); } else if (funcname == "selectionSort") { start = high_resolution_clock::now(); selectionSort(A,num_num); stop = high_resolution_clock::now(); } else if (funcname == "binSearches") { sort(A,A+num_num); start = high_resolution_clock::now(); binSearches(A,num_num); stop = high_resolution_clock::now(); } else if (funcname == "rmzeroes") { sort(A,A+num_num); for (int i=0; i

delete [] A; auto duration = duration_cast(stop-start); float dur = duration.count(); return dur; }

int main() { int num_iter; // Number of iterations int num_num; // Number of numbers in array string funcname; // Which function the user wants to run float dur, old_dur=1, ratio; cout << "How many iterations? "; cin >> num_iter; cout << "How many numbers to start with? "; cin >> num_num; cout << "Which function are you running? "; cin >> funcname;

for (int i=0; i

Could someone please help me with this.