The Mandrill and Baboon are two (fictitious) problems that accept a weighted graph and return an integer. Consider the reduction below, which reduces the Mandrill problem to the Baboon problem. Input: G = (V, E): weighted graph with n vertices and m edges Input: n, m: order and size of G Output Mandrill (G) Algorithm: Monkey Business H = Graph (n); for u elementof V do for v elementof V do if G.is Adjacent (u, v) then Let w be the weight of (u, v); if w >100 then H.addEdge(u, v, 5 + w/20); else if w > 25 then H.add Edge (u, v, Squareroot w) end end end end return Baboon H What is the worst-case time complexity of this reduction, not including the cost to compute Baboon(H)? You may assume that the squareroot in line 10 takes Theta (1) time to compute, and assume that we use an adjacency matrix to represent the graphs G and H. Suppose that we know that the complexity for Baboon is bounded above by O(B (m, n)) and below by Ohm b(m, n) for a graph with m edges and n vertices. What does the algorithm above prove about the complexity of Mandrill, assuming that B(m, n) and b (m, n) are both larger than your answer to question 1? Justify your answer. The Mandrill and Baboon are two (fictitious) problems that accept a weighted graph and return an integer. Consider the reduction below, which reduces the Mandrill problem to the Baboon problem. Input: G = (V, E): weighted graph with n vertices and m edges Input: n, m: order and size of G Output Mandrill (G) Algorithm: Monkey Business H = Graph (n); for u elementof V do for v elementof V do if G.is Adjacent (u, v) then Let w be the weight of (u, v); if w >100 then H.addEdge(u, v, 5 + w/20); else if w > 25 then H.add Edge (u, v, Squareroot w) end end end end return Baboon H What is the worst-case time complexity of this reduction, not including the cost to compute Baboon(H)? You may assume that the squareroot in line 10 takes Theta (1) time to compute, and assume that we use an adjacency matrix to represent the graphs G and H. Suppose that we know that the complexity for Baboon is bounded above by O(B (m, n)) and below by Ohm b(m, n) for a graph with m edges and n vertices. What does the algorithm above prove about the complexity of Mandrill, assuming that B(m, n) and b (m, n) are both larger than your answer to question 1? Justify your