Suppose you are given n = 3^k marbles that look identical, with one special marble that weighs more than the other marbles. You are also given a balancing scale that takes two items (or sets of items) and compares their weights. Design and analyze a divide and conquer algorithm to find the heavy marble using the balancing scale at most k times. Give the recurrence relation for the running time. Apply the Master Theorem to show that the running time is k.