Suppose you are given recurrences of the form T(n) = aT(n/b) + g(n), with T(1) =

Question

Suppose you are given recurrences of the form T(n) = aT(n/b) + g(n), with T(1) = d > 0 and g(n) > 0 for all n, and S(n) = aS(n/b) + g(n), with S(1) = 0 (and the same a, b, and g(n)). Is there any difference in the big Theta behavior of the solutions to the two recurrences? What does this say about the influence of the initial condition on the big Theta  behavior of such recurrences?

Explanation / Answer

in first case , T(n) have n>0 so it's value is also greater than zero . g(n) depend only how many times ur n split for search a number . in second case . s(n) have n=0 so it's value is zero .

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.