Updated Wed 4-2-2014
Unless explicitly stated in the problem or on this page, you should show work for all problems.
Problem 1a Hint: Reading Chapter 1 will be really useful here.
Problem 1b Hint: Reading Chapter 1 will also be really useful here.
Problem 1c You may use induction to prove 1.12a but it is not required.
Problem 2 You should be able to use the technique of expansion discussed in the lecture slides. In particular, look at slide 24 from lecture 2. For the recurrence: T(n) = 10 + T(n/2), the closed form is T(n) = 10 log n + 15.
The floor function might cause some confusion - but be sure not to ignore it for either part a or part b. For part a, just be sure to use it correctly in your calculations. For part b, here are a few things that may be useful in your calculations. Be sure to remember what the definition of floor means:
⌊ x ⌋ = m iff m ≤ x < m + 1
You may also find some of the rules here useful. Like the fact that floor is idempotent and also how nested divisions work. Regardless, your answer to part b should be exact, not in big-O notation and you should go back and check that your closed form gives you the exact same answers for T(1)- T(8) that you calculated in part a.
To show something is false, come up with a counter example. For part b, this means *functions* that would make the statement not be true (again, be sure to use the definition to show that it could not be true). For parts a, c, and d, if they were false you would show how you could *not* pick positive constants c and n0 to make it true. I realize that sounds a little strange in the abstract, but I think once you start working on it you will be able to see what I mean. Keep in mind various manipulations we can do to both sides of an equation like taking the log or treating each side as an exponent if the current way of looking at things is not obvious to you.