Note:  Worksheet problems are more like practice problems to hone your skills through better understanding the concepts.  They are easier than homework problems. Solution to every  problem should preferably  be typed  (or, very  legibly  written  in  hand  on letter size  pages). Plagiarism  in  any  form  will  be  strictly  dealt  with  following departmental policy. You should try to solve by yourself as much as possible. You can take help of study materials and book resources and office hours.

1.   For each of the following recurrences, give an expression for the runtime T (n) if the recurrence can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply. Remember to show every step clearly. [21*2 = 42]

T(n) = 3T(n/4) + n log n

T(n) = 3T(n/3) + n/2

T(n)_6T(n/3) + n² logn

T(n) = 4T(ti/2) + n/log n

T(n) = 64T(n/8) - n² logn