Assignment 2

So the second assignment is just two questions.

  I found it's easy to solve the first question by simply looking at the examples given, evaluate several other examples for different ns according to conditions given, then I'm able to write out the pattern, which is like a recursive call as we did for merge sort.

  Unwind it and then it's not difficult to find that it acts quiet like a Fibonacci sequence, so unwind it like a Fibonacci sequence in course notes, the most important thing to know is that the closed form of a Fibonacci sequence, without it, there's no way to start the induction proof.
 
  As for question two, since we want T(n) to be non-decreasing, then obviously the max between T(ceiling(n)) and T((floor(n))) has to be T(ceiling(n)), but we still need to use complete induction like the one shown in course notes to prove it's non-decreasing first, then unwind the pattern to get a closed form, and the last step is to prove the closed form in the way we did in CSC165, since it's a big-theta proof, we need to prove both big-oh and big-omega.