Draw the recursion tree for T(n) = T(n/3) + T(n/4) + Θ(n) to make an educated guess at a solution to the recurrence. Use the substitution method to prove your solution is correct. If we assume T(a) < T(b) for all a < b, how could we use the master method to solve this problem? Why can we not use the master method otherwise?
7. Captain Krik is a space traveler in search of a rare piece of technology called the MacGuffin. Unfortunately for Captain Krik, the MacGuffin could be on any one of an infinite number of planets (each identified by a unique positive integer), and Captain Krik needs to find the MacGuffin as quickly as possible. Each planet contains a wizard who will tell Captain Krik whether or not the MacGuffin is on a planet having a strictly higher planet identifier than their own. Supposing the MacGuffin resides on planet p, describe an algorithm to help Captain Krik find the MacGuffin by interviewing at most O(lg p) wizards. Your solution does not need to be in psuedocode for this problem. Captain Krik is a space traveler in search of a rare piece of technology called the MacGuffin. Unfortunately for Captain Krik, the MacGuffin could be on any one of an infinite number of planets (each identified by a unique positive integer), and Captain Krik needs to find the MacGuffin as quickly as possible. Each planet contains a wizard who will tell Captain Krik whether or not the MacGuffin is on a planet having a strictly higher planet identifier than their own. Supposing the MacGuffin resides on planet p , describe an algorithm to help Captain Krik find the MacGuffin by interviewing at most O ( lg p ) wizards. Your solution does not need to be in psuedocode for this problem.