3. (10 marks) Write out in some detail a divide-and-conquer solution to the perfect square problem. You may consider using the following header which is initially invoked as DCPerfectSquare(1, n, n). bool DCPerfectSquare (int low, int high, int n) 4. (2 marks) State the worst case time complexity of your solution in part 3 as a recurrence relation. 5. (4 marks) Using the Master Theorem, determine the exact order time complexity of your recurrence in part 4