Dynamic array expansion.

cpp.

Measuring time The std::clock() method returns the CPU time your process used since it started. To use it, you need to include the ctime header file as in the example below. The returned value does not make sense on its own. The difference between two values returned by clock denotes the time passed between the two function calls. Consequently, the following code measures how long function f() takes to execute. #include //used for cout and endl int main() { #include // used for set precision //clock_t type abstracts time #include // used for clock std::elock_t c_start - std::clock(); f(): // function does some time consuming work std::elock_t c_end - std::elock(); void 1() { //CLOCKS_PER_SEC constant is system dependent double d - 0; // denotes number of clocks per second double elapsed - 1000.0+(c_end-c_start)/ for (int n-o; n return 0; } 1 Problem 1: Dynamic array expansion A dynamic array (DA) starts with zero elements: a fixed capacity and zero size. When inserting an element in a DA either The resulting size of the DA is within its capacity, so the code places the element and incre- ments size; or The resulting size is greater than the capacity, so the code expands the DA by allocating twice the memory, copies the existing data into the newly allocated memory, discards the old data, places the element, increments size, and sets capacity. The code below is a simple implementation of a dynamic array of integers. struct DynArr ( unsigned int size, capacity: void insert(int t) { if (size >- capacity) (//grow the array unsigned int newcapacity - capacity.GROW_FACTOR; Win Styli A dynamic array (DA) starts with zero elements: a fixed capacity and zero size. When inserting an element in a DA either The resulting size of the DA is within its capacity, so the code places the element and incre- ments size; or The resulting size is greater than the capacity, so the code expands the DA by allocating twice the memory, copies the existing data into the newly allocated memory, discards the old data, places the element, increments size, and sets capacity. The code below is a simple implementation of a dynamic array of integers. struct DynArr ( void insert(int t) { int . data: if (size >- capacity) [//grow the array unsigned int size, capacity: unsigned int newcapacity - capacity.GROW_FACTOR; int. newdata - new int[newcapacity); // constructor for (int i=0; i capacity - newcapacity: //set capacity ) data[size] - t;//place new element size - size + 1;//increment size > Write code that uses DynArr to allocate and insert a large number of elements into a DynArr object. Use std::clock to measure the time needed to insert 1000, 2000, 3000, 4000, 5000, 200000 elements into the DynArt object. Change the way the array is expanded and instead of doubling the capacity, only increase the capacity by 10. Repeat measuring the time for 1000, 2000, 200000 insertions. What difference do you notice? Try to explain. Hint: try to chart the two sequences. Repeat the same exercise but now use the STL vector class instead of DynArr. Use the push_back method to insert the elements. . Compare the behavior of the vector insertions with the DynArr (with double growth) insertions. Try to explain the difference in runtime behavior if any