4. (a) Fill in the '?' to make the following statement true. n T(n) = 1.01 i=1 -i = O(?). (b) Use a recursion tree to compute an asymptotic solution for the recurrence G(n)G(2n/3) + G(n/3) +n. 5. Give asymptotic bounds for T(n) in each of the following recurrences. Assume any reasonable base cases in the recurrences below, for example, T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. (a) T(n) = 9T(n/3) + 225n (b) T(n)T(9n/10) + log n (c) T(n) = 3T(n/2) + n² √n (d) T(n) = T(n − 1) + n²
4. (a) Fill in the '?' to make the following statement true. n T(n) = 1.01 i=1 -i = O(?). (b) Use a recursion tree to compute an asymptotic solution for the recurrence G(n)G(2n/3) + G(n/3) +n. 5. Give asymptotic bounds for T(n) in each of the following recurrences. Assume any reasonable base cases in the recurrences below, for example, T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. (a) T(n) = 9T(n/3) + 225n (b) T(n)T(9n/10) + log n (c) T(n) = 3T(n/2) + n² √n (d) T(n) = T(n − 1) + n²
Related questions
Question
I need these questions and all their parts answered. Please show work
Transcribed Image Text:4. (a) Fill in the '?' to make the following statement true.
n
T(n) = 1.01
i=1
-i
=
O(?).
(b) Use a recursion tree to compute an asymptotic solution for the recurrence
G(n)G(2n/3) + G(n/3) +n.
5. Give asymptotic bounds for T(n) in each of the following recurrences. Assume any reasonable
base cases in the recurrences below, for example, T(n) is constant for n ≤ 2.
Make your
bounds as tight as possible, and justify your answers.
(a) T(n) = 9T(n/3) + 225n
(b) T(n)T(9n/10) + log n
(c) T(n) = 3T(n/2) + n² √n
(d) T(n) = T(n − 1) + n²
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
