COMP 3804 Study Guide - Fall 2019, Comprehensive Final Exam Notes - Asteroid Family, Time, Rela
1 Apr 2019
School
Department
Course
Professor
Document Summary
The master theorem applies to recurrences of the following form: T (n) = at (n/b) + f (n) where a 1 and b > 1 are constants and f (n) is an asymptotically positive function. Regularity condition: af (n/b) cf (n) for some constant c < 1 and all su ciently large n. For each of the following recurrences, give an expression for the runtime t (n) if the recurrence can be solved with the master theorem. We are in case 3, but the regularity condition is violated. (consider n = 2 k, where k is odd and arbitrarily large. For any such choice of n, you can show that c 3/2, thereby violating the regularity condition. ) Instructions: the exam consists of four questions, each worth 25 marks, you can do the rough work on the reverse/opposite side of the sheets.
