Write clearly.
Write your name and section clearly on the top of the first page.
Scan/photograph clearly.
If we can't read it, we will grade it as incorrect.
After you finish your answers, scan or carefully photograph your answer sheets
and create a single PDF with those images to upload
to the ELMS entry.
You cannot e-mail them to me.
We may only grade some subset of these, but you are expected to do them all.
For this homework you must use the recursion tree technique from class. I want you to be thinking in terms of the "tightest" Big-O() and the "tightest" Big-Ω that the recurrence tree technique gives when you do not think about the work in the leaves. For example, this means is that for Big-O it's fine to do a slight over-estimation (ie: pretend that all of the levels are 'full' so use the work-per-level pattern that starts at the top of the tree even for levels that aren't actually full) when working out the summations. (1) (a) What are the "tightest" Big-O() and Big-Ω of the run-time of a recursive function with the following recurrence: T(1)=1 T(n)=n+T(n/2)+n+T(n/4)+n If you feel it would be useful to make an assumption about n being a power or multiple of something, clearly state that assumption. We care about the constants that are natural to keep around (like log bases, things in exponents, etc). Your answer needs to show your tree structure, your work per level determination, and your calculations as you proceed from there. (b) How would your calculations change if I said that the recurrence was: T(n)=T(n/2)+T(n/4)+Θ(n) but didn't give you any more details about the Θ(n)? Provide this answer as a one to three line descriptive answer, NOT as a mathematical proof. (c) How would your calculations change if I said that the recurrence was: T(n)=log(n)+T(n/2)+n+T(n/4)+n Provide this answer as a one to three line descriptive answer, NOT as a mathematical proof. (2) What preliminary Big-O() and Big-Omega results would the recursion tree technique provide for the run-time of a recursive function with the following recurrence: T(1) = 1 T(n) = T(n/2)+T(2n/3)+8; If you feel it would be useful in the analysis, you can assume that n is a power or multiple of something you may do so, just tell us which power/multiple. As with (a) in question #1 above, we want to see your work, your log bases, constants in exponents, etc.