Please answer the true or false questions along with an explanation of why the answer was chosen.

(9) Answer True or False. 1. Any comparison based algorithm for sorting requires 2(n3) comparisons 2. Time complexity of Prim's algorithm (using a priority queue) is O(n log n), where n is the number of vertices and m is number of edges. 3. We can solve traveling salesman problem, exactly, in O(n2) time, on an n vertex graph. 4. The time complexity of dijkstra's algorithm is O(nlog n), where n is the number of vertices the graph 5. The time complexity of Kruskal's algorithm Using union and Find algorithm is O(n2), where n is the number of vertices