Answered: Solve the recursion by substitution:…

Engineering

Computer Science

Solve the recursion by substitution: T(n) = 3T(n/2)+ 5n where T(1)=1

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter15: Recursion

Section: Chapter Questions

Problem 7SA

See similar textbooks

Related questions

Q: Given the recursive definition: a1 = 2, a2 = 6 an = 2an-1 + 3an-2, n> 2, what is a6? O 256 O 162

A: Solution:

Q: The part of a problem that is solved with recursion is the case.a. baseb. iterativec. unknownd.…

A: Recursion is a process in which a function call itself. Three condition of recursion are 1) Function…

Q: Write a recursive method that will compute the number of even digits in anumber.

A: "Since you have not mention any programming language, so will write our program in C language". C…

Q: 7. A game is played by moving a marker ahead either 2 or 3 steps on a linear path. Let cn be the…

A: Actually, algorithm is an step by step process.

Q: (a) Give a recursive definition of F(n) where F(n) =1+2+3+....+n. (b) Find the value of a4 if a1 =…

A: Considering the given series F(n) = =1+2+3+....+n This series can be taken as the sum of first n…

Q: (a) Given two numbers x and y find product using recursion. Hint: x added to itself y times.

A: Answer(a)// C++ code is given below, explanation is given in comments#include…

Q: Question: Let t(x) be the number of primes that are <x. Show that T(x) is primitive recursive.

A: Let pi(x) be the number of primes that are <=x show that pi(x) is primitive recursive.

Q: If A is a non-zero real number and n is a non-negative integer, the fact A=A(n-1)x A can be used as…

A: Exponential

Q: Implement a recursive algorithm to find the n-th Fibonacci number using memoization.

A: # Function for nth Fibonacci number def Fibonacci(n): if n<= 0:…

Q: Solve tower of Hanio problem for N = 4, 5 & 6 using recursion. The call of recursion is as follows:…

A: Programming Language Used- C Language C code Tower of Hanoi Problem(for N=4, 5 and 6) using…

Q: 4. Perform Left Recursion Elimination for the following gram E à E +T|E-T|T Tà TF |F F à F * | C C à…

A: Consider the given Grammar : E→E+T | E-T | T T→TF | F F→F*|C C→a|b We can remove Unit Production…

Q: Let E(x) = 1 if x is a multiple of 3, E(x) = 0, otherwise. Show that E(x) is primitive recursive.

A: Let E(x) = 1 if x is a multiple of 3, E(x) = 0

Q: escribe a non recursive algorithm for enumerating all permutation of the number {1,2,....,n} in C+

A: ALGORITHM: Step 1: Start Step 2: Create a procedure combination which accepts two parameters a and b…

Q: Write a recursive mathematical definition for computing 2n for a positive integer n.

A: Given: Write a recursive mathematical definition for computing 2n for a positive integer n.

Q: Show the complete solution. 1. For each sequence, find a general term.: 1, 8, 27, 64,....

A: Given: Find a broad phrase for each sequence: 1, 8, 27, 64,....

Q: Examples: Find the tight bound of the following recursive functions, T(n). T(n)=9T(n/3)+n T(n)=…

A: the solution is an given below :

Q: Python: Using recursion to print half of the indent hourglass pattern.

A: Declare input variables. Using for loop, set the input value 10 and decrement it in each next step…

Q: T(1) = 1 T(n)= T(n - 1) + n² , n > 1

A: we need to find recessive equation for T(n)=T(n-1) +n2 using telescoping method

Q: A recursive definition for exponentiation on the non-negative integers is partially giver expt(k, 0)…

Q: Give a recursive definition for an (where n=1,2,3,...) if an=2n+5

A: Below is the recursive definition for an=2n+5: a1=7,a2=9........an=2n+5 Now from above we get :…

Q: Give a recursive deﬁnition for the set of all strings of 0’s and 1’s that contain exactly two and…

A: Here have to determine about math problem about recursive deﬁnition.

Q: By using a recursive function to find s value: S= 2/x - 4/x + 6/x – 8/x.. 2n/x

A: ALGORITHM:- 1. Take input from the user. 2. Pass these values to the series calculator function. 3.…

Q: Write a recursive mathematical definition for computing for a positive integer n and a real number…

A: PROGRAM CODE: import java.util.Scanner; public class Main{ public static int power(int x,int n) {…

Q: A game is played by moving a marker ahead either 2 or 3 steps on a linear path. Let cn be the number…

A: Answer : Pseudo Code in C++

Q: bottom up recursive solution to 1 + 2 + 3 +...+ n please show work step by step (dyanamic…

A: We have to find the recursive solution to find the sum of first natural no : 1 + 2 + 3 + 4 + 5 +6 +7…

Q: Given the recursive definition: a1 = 1, a2 = 4 an = an-2 + n?, n > 2, what is ag? O 120 O None of…

A: Solution:

Q: A set SS of strings of characters is defined recursively by aa and bb belong to SS . If xx belongs…

A: Given : A set S of strings of characters is defined recursively by a and b belong to S. If x…

Q: The Fibonacci series can be defined recursively as: F1 = 0; F2 = 1; and Fn = Fn-2 + Fn-1. Show…

A: Basis step: For n = 1 F1F2 = (1)(1) = 1 = 12 = F12 The proposition is true for n = 1.

Q: Draw a recursion tree for the following function for myFunc(5), then give the output of the int…

A: INTRODUCTION: Recursion tree is a type of pictorial representation of tree in which we consider the…

Q: Provide a recursive definition for the following set S.

A: Given :- Provide a recursive definition for thefollowing set S.S={2k3m5n E N | k, m, n E Z+}Z+ is…

Q: Eliminate Left Recursion from the following CFG. S-> SS + | (SS *)[ a|Ab| +B|E A-> AS|*Salb|AA |aS +…

A: Left recursion :- left recursion occur if the leftmost variable of its RHS is same as Variable of…

Q: ative) Recursive) 138240 Given big integer 8584803 (Iterative) (Recursive) e Given big intager 12345…

A: Big integer problem square number is a number in the form of op2, op2,op3, 4, 9, and 16 are square…

Q: using the recursion tree T(n) = 4T(n-1) + c, where c is a positive constant, and T(0)=0.

A: Using the recursion tree to solve the given function

Q: Apply the recursive GCD algorithm. Show the calls to gcd with the arguments for each recursive call…

A: #include <iostream>using namespace std;int gcd(int c, int d) { if (d == 0) //d=18…

Q: + n

A: given - PLS SHOW STEP BY STEP OF BOTTOM UP RECURSION SOLUTION TO 1 + 2 + 3 + ... + n

Q: Write a recursive mathematical definition for computing for a positive integer n.

A: Given: Write a recursive mathematical definition for computing for a positive integer n.

Q: n T(n) — 2T (п/2) + lg n

A: Provided the solution for above recurrence equation using a recursion tree and iterative…

Q: Label the Recursion Requirements. Show the Activation Stack for n = 4.

A: The answer is

Q: Find a non-recursive formula for f (n) : f (0) = 7, f (n) = 4f (n − 1)/9 for n ≥ 1

A: Given: To write the recursive formula.

Q: 2. Suppose the above algorithm performs a recursive call of size 75% for the first recursive call,…

A: Given :- Suppose the above algorithm performs a recursive call of size 75% for the first recursive…

Q: Write a recursive program to find factorial of 10 and print it. In go language

A: go lang Program for above : package main import "fmt" func Calculate_factorial(x uint) uint {…

Q: „n = 1 T(n) ={ 8T("/2) + dn² ,n> 1

A: MASTER theorem The master theorem is utilized in calculating the time complexity of recurrence…

Concept explainers

Computational Systems

The computation systems can be defined as the systems that are capable of solving a problem that includes calculations either mathematical or logical, and are able to produce the result as an output. For example, a simple calculator that is given a set of numbers and operators as input and produces the result as an output can be defined as a computational system. The above example is a simple illustration only, the computational systems range from simple devices to complex devices such as the systems that control the SpaceX companies, Starlink satellites which are being quite recently seen in the skies at many places globally.

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.