1. For each one of the following summaries, state whether the algorithm runs in polynomial time or not. Assume that the algorithm's input is n integers. a. Sort n integers in O(n log n) time. b. Sort n integers in the range between 0 and k-1 in O(n + k) time. c. Sort n integers in the range between 0 and nd-1, where d is a constant, in O(n) time. d. Given a weighted directed graph G=(V, E) with n=IVI nodes and m=El arcs and with maximum arc length U, find the shortest paths from seV in time O((n + m)2). e. Given a weighted directed graph G=(V, E) with n=1Vnodes and m=|El arcs and with maximum arc length U, find the shortest paths from sev in time O(n + m + U). f. Given a weighted directed graph G=(V, E) with n=IVI nodes and m=lEl arcs and with maximum arc length U, find the shortest paths from seV in time O((n + m) log U)