Problem Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n < 2. Make your bounds as tight as possible, and justify your answers. 1. T(n) = 3T(n/4) + Vn 2. T(n) = 4T(n/2) + n² %3D %3D 3. T(n) = 2T(n/3) + nlg n %3D 4. T(n) = 2T(n/2) + n/ lg n 5. T(n) = T(n- 1) +1/n %3D

Problem Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n < 2. Make your bounds as tight as possible, and justify your answers. 1. T(n) = 3T(n/4) + Vn 2. T(n) = 4T(n/2) + n² %3D %3D 3. T(n) = 2T(n/3) + nlg n %3D 4. T(n) = 2T(n/2) + n/ lg n 5. T(n) = T(n- 1) +1/n %3D

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Solve recurrence relation using substitution(i.e. proof by induction), to show that for some c > 0, T(n) ≤ cn2 for large enough n, where T(n) = 3T(n/2) + 2T(n)
Consider the following recurrence relation: T(0) = 2, T(1) = 5, T(n) = 27(n – 1) – T(n – 2) for n>1 Write out the first few values T(0), T(1), T(2),...,. Make a guess about the closed form of T(n) and then prove that it is a closed form for T(n) using induction.
Given the following recurrence, find the growth rate of T(n):T(n) = 4T(n/2) + 6n3 with T(1) = Θ(1)
Use the substitution method to show that the recurrence defined by T(n) = 2T(n/3) + Θ(n) hassolution T(n) = Θ(n).
Let T(n) be defined by the first-order linear recurrence T(n) = 2T(n-1) +8 Suppose it is given that T(2) = c. Compute T(0) by iterating backwards and express your answer in terms of c. T(0) =
Consider the following recurrence: T(1)=1; T(n) = 2.T()+n, for n> 1, n a power of 3. =..... Find T(27) by substitution, starting with n = 1, n = 65 2 169 29 15 6
Please explain Give asymptotic upper and lower bounds for each of the following recurrences. Justify your answer. T(n)=√nT(√n)+n
Solve the recurrence relations below. Fill in the blanks for the closed form expression and rate of growth. n = 0 T(n) = { ½ (n ¸T(n − 1) + n² + 2, n>0 Express final answers in simplest form. Closed form expression of T(n)= Rate of Growth: (
Find a tight bound solution for the following recurrence: T(n) = 4 T(n/2) + c n (c is a positive constant) That is, find a function g(n) such that T(n) ∊ Θ(g(n)). For convenience, you may assume that n is a power of 2, i.e., n=2k for some positive integer k. Justify your answer. [Note: Read question 1-(2) first before writing your answer] Prove your answer in 1-(1) either using the iteration method or using the substitution method.
Let f (f(n) and g(n)) be asymptotically nonnegative functions. Using the basic definition of Θ notation, prove that max(f(n), g(n)) = Θ(f(n) + g(n)),
Give asymptotically tight upper and lower bounds for T (n) in each of the following algorithmic recurrences. Justify your answers. A. T(n) T(7n/10) + n B. T(n) C. T(n) = = = D. T(n) = 2 16T(n/4) + n² 2T(n/4) + √n n² √n 4T(n/2) + n E. T(n) = 3T((n/3) - 2) + n/2 (Hint: think about how you can use an assumption about the importance of the -2 to apply the Masters Theorem)
Given t(n) = 3n³, which of the following functions g(n) satisfy t(n) = O(g(n))? Select one or more answers. g(n)=n g(n) = en O g(n) = n² g(n) = log(n) O g(n) = n³ O g(n) = n!