The Art of Statistics notes

1 Problem 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T(n) = 2T( n 2 ) + log(n) for n > 1, 0 otherwise • T(n) = O(n) • T(n) = O(nlogn) • T(n) = O(n 2 ) • T(n) = O(logn) 1.1 Rationale This recurrence relation can be tricky to solve using iterative substitution or tree-based methods. It’s best to use the Master theorem here. Recall the form: T(n) = aT(n/b) + f(n) Since f(n) = log(n) = n  where  < log2(2) = 1...

1 Problem 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T(n) = 2T( n 2 ) + log(n) for n > 1, 0 otherwise • T(n) = O(n) • T(n) = O(nlogn) • T(n) = O(n 2 ) • T(n) = O(logn) 1.1 Rationale This recurrence relation can be tricky to solve using iterative substitution or tree-based methods. It’s best to use the Master theorem here. Recall the form: T(n) = aT(n/b) + f(n) Since f(n) = log(n) = n  where  < log2(2) = 1...