5th_nov_Recurssion releation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c095f47b-3623-4db6-ab06-15729435f833",
   "metadata": {},
   "source": [
    "Q1. Find the value of T(2) for the recurrence relation T(n) = 3T(n-1) + 12n, given that T(0)=5."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "081305c9-7fe5-42c0-9516-246944c1eced",
   "metadata": {},
   "source": [
    "We are given the recurrence relation:\n",
    " T(n)=3T(n−1)+12n\n",
    "with the initial condition \n",
    " T(0)=5. We need to find\n",
    "\n",
    "Step-by-step calculation:\n",
    "\n",
    "Step 1: Calculate \n",
    " \n",
    "Using the recurrence relation for  n=1:\n",
    " T(1)=3T(0)+12×1\n",
    "Substitute the value of T(0)=5:\n",
    "   \n",
    "T(1)=3×5+12=15+12=27\n",
    "Step 2: Calculate \n",
    "\n",
    "Now, using the recurrence relation for \n",
    "\n",
    "T(2)=3T(1)+12×2\n",
    "Substitute the value of T(1)=27: \n",
    "T(2)=3×27+24=81+24=105\n",
    "Final Answer: \n",
    "T(2)=105"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abf17e0d-7d06-4d1a-b6ec-be006f3808fd",
   "metadata": {},
   "source": [
    "Q2. Given a recurrence relation, solve it using the substitution method:\n",
    "a. T(n) = T(n-1) + c\n",
    "b. T(n) = 2T(n/2) + n\n",
    "c. T(n) = 2T(n/2) + c\n",
    "d. T(n) = T(n/2) + c"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "491c1554-00c2-4271-9910-29f05ac86a4d",
   "metadata": {},
   "source": [
    "The substitution method involves solving a recurrence relation by guessing the solution and proving it by induction. Let's solve each of the given recurrence relations one by one using this method.\n",
    "\n",
    "a. T(n)=T(n−1)+c\n",
    "This recurrence can be solved step by step by substituting values for T(n).\n",
    "\n",
    "Substitute for T(n−1) in the recurrence: T(n)=T(n−1)+c \n",
    "\n",
    "substitute this in for T(n−1)=T(n−2)+c\n",
    "\n",
    "(substitute this in for T(n−1))\n",
    "\n",
    "T(n)=T(n−2)+c+c=T(n−2)+2c\n",
    "Continuing this for \n",
    "\n",
    "k steps:\n",
    "T(n)=T(n−k)+kc\n",
    "Base Case: When \n",
    "T(0)=T(0)+kc=T(0)+nc.\n",
    "\n",
    "Now, using the fact that \n",
    " \n",
    "T(0)=T(0) by definition:\n",
    "\n",
    " \n",
    "T(n)=T(0)+nc\n",
    "Thus, the general solution for this recurrence is:\n",
    "\n",
    " \n",
    "T(n)=T(0)+nc\n",
    "b. \n",
    " \n",
    "T(n)=2T(n/2)+n\n",
    "This is a divide-and-conquer recurrence. Let's solve it by applying the substitution method.\n",
    "\n",
    "Substitute for \n",
    " \n",
    "T(n)=2T(n/2)+n\n",
    "Substituting \n",
    " \n",
    "T(n/2)=2T(n/4)+n/2:\n",
    " \n",
    "T(n)=2(2T(n/4)+n/2)+n=4T(n/4)+n+n\n",
    "Continuing this process:\n",
    " \n",
    "T(n)=8T(n/8)+3n\n",
    " \n",
    "T(n)=16T(n/16)+4n\n",
    "After \n",
    " \n",
    "k steps, we get:\n",
    " T(n)=2 \n",
    "k\n",
    " T(n/2 \n",
    "k\n",
    " )+kn\n",
    "Base Case: When \n",
    " \n",
    "n=1, we have \n",
    " \n",
    "T(1)=d (a constant).\n",
    "\n",
    "To find \n",
    " \n",
    "k where \n",
    " \n",
    "n/2 \n",
    "k=1, solve:\n",
    " \n",
    "n/2 \n",
    "k=1⟹k=log \n",
    "2   \n",
    "Substituting into the formula:\n",
    "\n",
    "T(n)=2 \n",
    "log2\n",
    " T(1)+nlog \n",
    " n=nT(1)+nlog \n",
    "Therefore, the solution is- T(n)=O(nlogn)\n",
    "\n",
    "c. T(n)=2T(n/2)+c\n",
    "This is another divide-and-conquer recurrence, similar to part (b), but with a constant instead of a linear term.\n",
    "\n",
    "Substitute for \n",
    "T(n)=2T(n/2)+c\n",
    "Substituting\n",
    "\n",
    "T(n/2)=2T(n/4)+c:\n",
    "T(n)=2(2T(n/4)+c)+c=4T(n/4)+2c+c=4T(n/4)+3c\n",
    "Continuing this process:\n",
    "\n",
    "T(n)=8T(n/8)+7c\n",
    "Afterk steps, we get:\n",
    "\n",
    "T(n)=2k\n",
    "T(n/2k)+(2k−1)c\n",
    "Base Case: When \n",
    "n=1, we have \n",
    "T(1)=d.\n",
    "To find \n",
    "k where \n",
    "n/2k =1, solve:\n",
    "n/2k=1⟹k=log2\n",
    "\n",
    "Substituting into the formula:\n",
    "T(n)=2log2n\n",
    "T(1)+(2log2n−1)c=nT(1)+(n−1)c\n",
    "Therefore, the solution is:\n",
    "\n",
    "\n",
    "T(n)=T(n/2)+c\n",
    "This is similar to the recurrence from part (c), but the recurrence only has a constant term (no multiplication by 2).\n",
    "\n",
    "Substitute for T(n)=T(n/2)+c\n",
    "Substituting T(n/2)=T(n/4)+c:\n",
    "\n",
    "T(n)=T(n/4)+c+c=T(n/4)+2c\n",
    "Continuing this process:\n",
    "\n",
    "T(n)=T(n/8)+3c\n",
    "After k steps, we get:\n",
    "\n",
    "T(n)=T(n/2k)+kc\n",
    "Base Case: When \n",
    "n=1, we have \n",
    "T(1)=d.\n",
    "\n",
    "To find k where n/2k=1, solve:\n",
    "Substituting into the formula:\n",
    "\n",
    "T(n)=T(1)+log2\n",
    "Therefore, the solution is:\n",
    "T(n)=O(logn)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22f00466-4b60-455b-ad69-fc95008dc755",
   "metadata": {},
   "source": [
    " Q3. Given a recurrence relation, solve it using the recursive tree approach:\n",
    "a. T(n) = 2T(n-1) +1\n",
    "b. T(n) = 2T(n/2) + n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4db964a3-b4af-43da-bcca-0b4b934bc19c",
   "metadata": {},
   "source": [
    "The recursive tree method is a visual approach used to solve recurrence relations. This method involves expanding the recurrence step by step and representing it as a tree, where each level of the tree corresponds to a recursive call, and the total cost is the sum of costs across all levels.\n",
    "\n",
    "Let's solve each recurrence relation using this approach:\n",
    " \n",
    "T(n)=2T(n−1)+1\n",
    "This recurrence relation is of the form where each call splits into two smaller subproblems (with \n",
    " \n",
    "1\n",
    "n−1) plus a constant cost of 1.\n",
    "\n",
    "Step 1: Expanding the recurrence\n",
    "Start with the given recurrence:\n",
    "\n",
    "\n",
    "T(n)=2T(n−1)+1\n",
    "Expand this further:\n",
    "\n",
    " \n",
    "T(n−1)=2T(n−2)+1\n",
    "Substitute this into the original recurrence:\n",
    " \n",
    "T(n)=2(2T(n−2)+1)+1=4T(n−2)+2+1\n",
    "Now, expand \n",
    " \n",
    "T(n−2):\n",
    " \n",
    "T(n−2)=2T(n−3)+1\n",
    "Substitute this into the previous expression:\n",
    " \n",
    " \n",
    "T(n)=4(2T(n−3)+1)+3=8T(n−3)+4+3\n",
    "Step 2: Identify the pattern\n",
    "By continuing this process, we can see the recurrence tree starts developing as:\n",
    " T(n)=2k\n",
    "T(n−k)+(2k−1)\n",
    "At each level of the tree, the number of calls doubles (since 2\n",
    " \n",
    "2T(n−k)), and the work done at each level adds up to a total of\n",
    "Step 3: Base Case\n",
    "We stop when 0\n",
    "n−k=0. So, when  \n",
    "k=n, the recurrence reaches the base case:\n",
    " \n",
    "(constant)\n",
    "T(0)=c(constant)\n",
    "Thus, when \n",
    " \n",
    "k=n, we have:\n",
    " \n",
    " \n",
    "T(n)=2nT(0)+(2n−1)\n",
    "Since \n",
    " \n",
    "T(0)=c, we get:\n",
    "T(n)=2nc+(2n−1)\n",
    "Step 4: Asymptotic Complexity\n",
    "The dominant term here is 2n\n",
    " So, the asymptotic complexity is: \n",
    "T(n)=2T(n/2)+n\n",
    "This is a standard divide-and-conquer recurrence that splits the problem into two subproblems, each of size \n",
    " \n",
    "n/2, plus a linear work cost \n",
    " \n",
    "n at each level.\n",
    "\n",
    "Step 1: Expanding the recurrence\n",
    "Start with the given recurrence:\n",
    " \n",
    "T(n)=2T(n/2)+n\n",
    "ExpandT(n/2):\n",
    "\n",
    "T(n/2)=2T(n/4)+n/2\n",
    "Substitute this into the original recurrence:\n",
    " \n",
    "T(n)=2(2T(n/4)+n/2)+n=4T(n/4)+n+n\n",
    "Now, expand (n/4):\n",
    " \n",
    " \n",
    "T(n/4)=2T(n/8)+n/4\n",
    "Substitute this into the previous expression:\n",
    "  \n",
    "T(n)=4(2T(n/8)+n/4)+2n=8T(n/8)+n+2n\n",
    "Step 2: Identify the pattern\n",
    "By continuing this process, we see that at each level of recursion, the size of the subproblems is halved, and the work done at each level is proportional to \n",
    "At level \n",
    " \n",
    "k, the size of the subproblem is \n",
    "\n",
    "k×(n/2k)=n.\n",
    "\n",
    "Thus, at each level, we do \n",
    " \n",
    "n work, and there are \n",
    "log2\n",
    " \n",
    " n levels in total (because the size of the subproblem halves at each level).\n",
    "\n",
    "Step 3: Summing the work at all levels\n",
    "At each level, the work done is \n",
    " \n",
    "n. Since there are \n",
    "log\n",
    " \n",
    " n levels, the total work done is:\n",
    "\n",
    "Total work=n×log2\n",
    "\n",
    "Step 4: Asymptotic Complexity\n",
    "Therefore, the time complexity of this recurrence is:\n",
    " \n",
    "T(n)=O(nlogn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "480337f0-ad01-4e42-b10e-7791af05ffa7",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}