Question

Consider using a vector of vectors to represent the adjacency list instead of a vector of lists. For each function from part b, c and ds, note if the runtime would change and justify your answer; i.e. explain why the runtime is the same or different
part b, c, d are functions. The function for part b sorts the list before inserting it into the vector. Part C compares two list and checks for common elements. Lastly, Part D if there are common elements then they merge the two list together.

Edit: This is in c++

Answer 1

b. For this part, the time complexity would be the same. As earlier, we need to sort list but now we would need to sort vector. But the time complexity of both the operations is O(nlong(n)), if merge sort is used in both the cases.

c. For this too the time complexity would be same, as we have the sorted list and vector, so we would need to traverse the list and vector linear in both the cases to find the common elements if present so for both the cases we will have the time complexity as O(n).

d. For this case, the time complexity would not be same, as in the case of the list we would need to traverse the full list in order to append the common element at the end of the list, whereas in the case of the vector we can do this operation in constant time complexity. Thus in case of vectors of the vector, the time taken would be less in comparison of the vector of lists.

Thanks