Estimate the maximum amount of time (in seconds) that would be required for the WHILE loop in the weighted quick union implementation given below to solve a problem with 10⁶ objects and 10⁹ input pairs, on a computer capable of executing 10⁹ instructions per second. Assume that each iteration of thewhile loop requires at most 100 instructions.

#include #include #define N .... // whatever value N should have for the given problem /* returns the set id of the object. */ int find(int object, int id[]) { int next_object; next_object = id[object]; while (next_object != id[next_object]) { next_object = id[next_object]; } return next_object; } void set_union(int set_id1, int set_id2, int id[], int size, int size_arr[]) { if (size_arr[set_id1] < size_arr[set_id2]) { id[set_id1] = set_id2; size_arr[set_id2] = size_arr[set_id1] + size_arr[set_id2]; } else { id[set_id2] = set_id1; size_arr[set_id1] = size_arr[set_id1] + size_arr[set_id2]; } } int main() { int p, q, i, id[N], p_id, q_id, size_arr[N]; // initialize ids and size for (i = 0; i < N; i++) // DO NOT compute the runtime for this loop { id[i] = i; size_arr[i] = 1; } // read pairs and keep/update connected components information printf("Enter pairs p q: "); while (scanf("%d %d", &p, &q) == 2) // compute the runtime for this loop { p_id = find(p, id); q_id = find(q, id); if (p_id == q_id) { printf(" %d and %d were on the same set ", p, q); print_array_int(id, N); continue; } set_union(p_id, q_id, id, N, size_arr); printf(" %d %d link led to set union ", p, q); } return 0; }