Answered: Solve the recursion by substitution:…

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

Related questions

Concept explainers

Question

100%

Solve the recursion by substitution:

T(n) = 3T(n/2)+ 5n where T(1)=1

Expert Solution

Step 1

Given Equation: T(n) =3T(n/2) + 5n

$T (n) = 3 T (n / 2) + 5 n - - - - 1 T (\frac{n}{2}) = 3 T (\frac{n}{4}) + 5 (\frac{n}{2}) - - - 2 s u b s t i t u t e e q u a t i o n 2 i n 1 T (n) = 3 (3 T (\frac{n}{4}) + 5 (\frac{n}{2})) + 5 n = 9 T (\frac{n}{4}) + 3 (\frac{5 n}{2}) + 5 n - - - - 3 T (\frac{n}{4}) = 3 T (\frac{n}{8}) + 5 (\frac{n}{4}) - - - - 4 S u b s t i t u t e e q u a t i o n 4 i n 3 T (n) = 9 (3 T (\frac{n}{8}) + 5 (\frac{n}{4})) + 3 (\frac{5 n}{2}) + 5 n = 27 T (\frac{n}{8}) + 9 (\frac{5 n}{4}) + 3 (\frac{5 n}{2}) + 5 n = 3^{3} T (\frac{n}{2^{3}}) + 3^{2} (\frac{5 n}{2^{2}}) + 3 (\frac{5 n}{2}) + 5 n - - - - 5 F o r K, T (n) = 3^{k} T (\frac{n}{2^{k}}) + 3^{k} (\frac{5 n}{2^{k}}) + . . . . . . . . . . + 3^{2} (\frac{5 n}{2^{2}}) + 3 (\frac{5 n}{2}) + 5 n T (n) = 3^{k} T (\frac{n}{2^{k}}) + 5 n \sum_{k = 0}^{n - 1} (\frac{3^{k}}{2^{k}}) - - - - - 6$

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions