Answer question 2 with the format given please

Q2. The following algorithm returns the product of two numbers, a and b. The parameters x and y are natural numbers. First, prove the correctness of the algorithm. Then, analyze the time complexity of the algorithm in the worst case scenario. function mult(a, b) if b = 0: return 0 else if bis odd: return (mult (2a, b/2 ) +a) else: return (mult(2a, b/2)) Loop Invariants To prove correctness using loop invariant, we must show: Base case . Inductive step Initialization: The invariant is true prior to the first iteration of the loop. Maintenance: If the invariant is true before an iteration of the loop, it remains true before the next iteration. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct