one approach to implementing an array-based list where the list size is unknown is to let the array grow and shrink this is known as dynamic array when necessarywe can grow or shrink the array by copying the array' contents to new array if we are careful about the size of the new arraythis copy operation can be done rarely enough so as not to affect the amortized cost of the operations (awhat is the amortized cost of inserting elements into the list if the array is initially of size and we double the array size whenever the number of elements that we wish to store exceeds the size of the arrayassume that the insert itself cost ( time per operation and so we are just concerned with minimizing the copy time to the new array (bconsider an underflow strategy that cuts the array size in half whenever the array falls below half full give an example where this strategy leads to bad amortized cost againwe are only interested in measuring the time of the array copy operations (cgive better underflow strategy than that suggested in part (byour goal is to find strategy whose amortized analysis shows that array copy requires (ntime for series of operations recall that two vertices in an undirected graph are in the same connected component if there is path connecting them good algorithm to find the connected components of an undirected graph begins by calling dfs on the first vertex all vertices reached by the dfs are in the same connected component and are so marked we then look through the vertex mark array until an unmarked vertex is found again calling the dfs on iall vertices reachable from are in second connected component we continue working through the mark array until all vertices have been assigned to some connected component sketch of the algorithm is as followsstatic void concom(graph gint ifor ( = < () ++/for vertices in graph setmark( )/vertex in no component int comp /current component for ( = < () ++if ( getmark( = /start new component dfs component(gicomp++)for ( = < () ++out append( getmark( ")static void dfs component(graph gint vint comp