Scribd
Upload
4 views1 page

Tutorial Week3 Thursday

This document outlines a tutorial assignment for the BTech course CSET244 on Design and Analysis of Algorithms for the 2024-2025 semester. It includes four questions focused on solving recurrence relations using various methods such as substitution, change of variable, master theorem, and recursion tree. Each question requires students to provide a Θ bound for the given recurrence relations.

Uploaded by

vikrammadhad
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Tutorial Week3 Thursday

This document outlines a tutorial assignment for the BTech course CSET244 on Design and Analysis of Algorithms for the 2024-2025 semester. It includes four questions focused on solving recurrence relations using various methods such as substitution, change of variable, master theorem, and recursion tree. Each question requires students to provide a Θ bound for the given recurrence relations.

Uploaded by

vikrammadhad
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Course/ Batch: BTech/ SCSET Course Type: Core

Course Code: CSET244 Course Name: Design and Analysis of Algorithms


Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 3

Tutorial title: Solving Recurrence Relation

CO Mapping

Question no CO1 CO2 CO3


Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Solve the following recurrence relations using substitution method and give a  bound for each of
them.
(i) T(n) = T(n-1) + n2 for n>0, with T(0)=10
(ii) T(n) = 3T(n – 1) + 1 for n >1, with T(1) = 1 and T(0)=0.

Q2. Solve the following recurrence relation using change of variable method and give a  bound for it.
T(n) = √nT(√n) + n

Q3. Give (.) bounds for T(n) in each of the following recurrence relations using master theorem.
𝑛
(i) T(n) = 2T( ) + nlogn
2
𝑛
(ii) T(n) = 4T(16) + √n

Q4. Find the (.) bounds for T(n) of the following recurrence relations using the recursion tree method.
T(n) = T(n/3) + T(2n/3) + n

You might also like