Algorithm Watershed Function & Iteration Method Questions

Problem 1
Recurrence
Define T (n) for n ∈ Z+ by the recurrence
(
0
for n = 1
T (n) =


n
T ⌈ 2 ⌉ + 1 for n ≥ 2
(1)
Prove that T (n) ≥ log(n) for all n ≥ 1, and hence, T (n) = Ω(log(n)).
Problem 2
Substitution method
Use the substitution method to show that the solution to
(
2
if n = 1, 2
s(n) =
 n 

9S 3 + 1 if n ≥ 3
(2)
satisfies S(n) = O(n2 ).
.
Problem 3
Define T (n) by the recurrence
(
21
if 1 ≤ n < 15 T (n) =  n 
T 2 + 6 if n ≥ 15 Use the iteration method to find the exact solution to this recurrence, and then determine an asymptotic solution. Problem 4 Iteration method Consider the following recurrence relation:  T (n) = 8T 4n 3  +n Apply the Master Theorem to find the tight asymptotic bounds for T (n). Problem 5 Recursive algorithm Design a recursive algorithm called exterma(A, p, r) that finds and returns the ordered pair (min(A[p..r]),   max(A[p..r])). Your algorithm should perform exactly 3n − 2 array comparisons on an input array of 2 length n. Problem 5 [Recursive algorithm] continued on next page. . . 1) Write algorithm in pseudocode. 2) Prove the correctness of your algorithm by induction on m = r − p + 1, the length of the subarray A[p..r].   3) Write a recurrence for the number of comparisons performed on A[1, ..n] and show that T (n) = 3n 2 −2 is the solution.