{"id":3177,"date":"2021-06-10T00:21:00","date_gmt":"2021-06-09T18:51:00","guid":{"rendered":"https:\/\/manorinfinity.com\/blog\/recurrence-relation-substitution-method-bitsofcs\/"},"modified":"2021-06-10T00:21:00","modified_gmt":"2021-06-09T18:51:00","slug":"recurrence-relation-substitution-method-bitsofcs","status":"publish","type":"post","link":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/","title":{"rendered":"Recurrence Relation | Substitution Method | BitsOfCS"},"content":{"rendered":"


<\/span><\/p>\n<\/p>\n

<\/p>\n

Recurrence Relation:<\/span><\/span><\/h1>\n

A recurrence relation is a equation or inequality that express a function in terms of its value on a smaller input.<\/span><\/span><\/p>\n

<\/span><\/span><\/span><\/p>\n

How to solve these recurrences? any idea?<\/span><\/span><\/p>\n

So, there are three ways to solve the recurrence relations.<\/span><\/span><\/p>\n

1. Substitution Method<\/span><\/span><\/p>\n

2. Recursion Tree Method (Iteration Method)<\/span><\/span><\/p>\n

3. Master Theorem<\/span><\/span><\/p>\n

<\/span><\/span><\/p>\n

<\/a><\/span>
<\/span><\/span><\/p>\n

Substitution Method:<\/span><\/span><\/h2>\n

In this method, we solve a recurrence relation mathematically(trying to prove it by induction).<\/span><\/span><\/p>\n

Example 1- <\/span>Find the time complexity of the below recurrence.<\/span><\/span><\/p>\n

T(n) = n + T(n-1) ; n>1<\/span><\/span><\/p>\n

T(n) = 1         ; n=1<\/span><\/span><\/p>\n

Explanation: <\/span><\/span><\/p>\n

Using substitution method,<\/span><\/span><\/p>\n

T(n) = n + T(n-1)…..eq1<\/span><\/span><\/p>\n

putting n = n-1 in eq1<\/span><\/span><\/p>\n

T(n-1) = (n-1) + T(n-2)…..eq2<\/span><\/span><\/p>\n

again putting n = n-1 in eq2<\/span><\/span><\/p>\n

T(n-2) = (n-2) + T(n-3)…..eq3<\/span><\/span><\/p>\n

putting eq2 –> eq1<\/span><\/span><\/p>\n

T(n) = n + (n-1) + T(n-2)…..eq4<\/span><\/span><\/p>\n

putting eq3 –> eq4<\/span><\/span><\/p>\n

T(n) = n + (n-1) + (n-2) + T(n-3)<\/span><\/span><\/p>\n

.<\/span><\/span><\/p>\n

.<\/span><\/span><\/p>\n

T(n) = n + (n-1) + (n-2) +…..+ (n-k) + T(n-(k+1))<\/span><\/span><\/p>\n

putting,<\/span><\/span><\/p>\n

n-(k+1) = 1<\/span><\/span><\/p>\n

n-k-1 = 1<\/span><\/span><\/p>\n

k = n-2<\/span><\/span><\/p>\n

T(n) = n + (n-1) + (n-2) +…..+ (n-(n-2)) + T(n-(n-2+1))<\/span><\/span><\/p>\n

T(n) = n + (n-1) + (n-2) +…..+ 2 + 1<\/span><\/span><\/p>\n

T(n) = n(n+1)\/2<\/span><\/span><\/p>\n

T(n) = (n<\/span>2<\/span><\/span> + n)\/2<\/span><\/span><\/p>\n

T(n) = <\/span>O(n<\/span>2<\/span><\/span>)<\/span><\/span><\/p>\n


<\/span><\/p>\n

Example 2- <\/span>Find the time complexity of the below recurrence.<\/span><\/span><\/p>\n

T(n) = 2T(n-1) – 1 ; n>0<\/span><\/span><\/p>\n

  T(n) = 1 ; otherwise (n=0)<\/span><\/span><\/p>\n

Explanation:<\/span><\/span><\/p>\n

Using substitution method,<\/span><\/span><\/p>\n

T(n) = 2T(n-1) – 1…..eq1<\/span><\/span><\/p>\n

putting n = n-1 in eq1<\/span><\/span><\/p>\n

T(n-1) = 2T(n-2) – 1<\/span>…..eq2<\/span><\/span><\/p>\n

again putting n = n-1 in eq2<\/span><\/span><\/p>\n

T(n-2) = 2T(n-3) – 1<\/span>…..eq3<\/span><\/span><\/p>\n

putting eq2 –> eq1<\/span><\/span><\/p>\n

T(n) = 2[<\/span>2T(n-2) – 1] – 1<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>2<\/span><\/span> T(n-2) – 2 – 1…..eq4<\/span><\/span><\/p>\n

putting eq3 –> eq4<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>2<\/span><\/span> [2T(n-3) – 1] – 2 – 1<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>3<\/span><\/span> T(n-3) – 2<\/span>2<\/span><\/span> – 2 – 1<\/span><\/span><\/p>\n

.<\/span><\/span><\/p>\n

.<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>k<\/span><\/span> T(n-k) – 2<\/span>k-1 <\/span><\/span>-……- 2<\/span>2 <\/span><\/span>– 2 – 1<\/span><\/span><\/p>\n

putting,<\/span><\/span><\/p>\n

n-k = 0<\/span><\/span><\/p>\n

n = k or k = n<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>n<\/span><\/span> T(n-n) – 2<\/span>n-1 <\/span><\/span>-……- 2<\/span>2 <\/span><\/span>– 2 – 1<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>n<\/span><\/span> * 1 – 2<\/span>n-1 <\/span><\/span>-……- 2<\/span>2 <\/span><\/span>– 2 – 1<\/span><\/span><\/p>\n

T(n) = <\/span>2<\/span>n<\/span><\/span> – (2<\/span>n-1 <\/span><\/span>+……+ 2<\/span>2 <\/span><\/span>+ 2 + 1) <– (geometric progression or G.P.) <\/span><\/span><\/p>\n

Since <\/span><\/span>(<\/span>2<\/span>n-1 <\/span><\/span>+……+ 2<\/span>2 <\/span><\/span>+ 2 + 1) = <\/span>2<\/span>n<\/span><\/span> – 1<\/span><\/span><\/p>\n

T(n) = 2<\/span>n<\/span><\/span> –<\/span>(2<\/span>n<\/span><\/span> – 1)<\/span><\/span><\/p>\n

T(n) = <\/span>O(1) <\/span><\/span><\/p>\n

 <\/span><\/span><\/p>\n

Example 3- <\/span>Find the time complexity of the below recurrence.<\/span><\/span><\/p>\n

T(n) = T(n-1)*n ; n>1<\/span><\/span><\/p>\n

T(n) = 1       ; n=1<\/span><\/span><\/p>\n

Explanation:<\/span><\/span><\/p>\n

Using substitution method,<\/span><\/span><\/p>\n

T(n) = T(n-1)*n…..eq1<\/span><\/span><\/p>\n

putting n = n-1 in eq1<\/span><\/span><\/p>\n

T(n-1) = T(n-2)*(n-1)<\/span>…..eq2<\/span><\/span><\/p>\n

again putting n = n-1 in eq2<\/span><\/span><\/p>\n

T(n-2) = T(n-3)*(n-2)<\/span>…..eq3<\/span><\/span><\/p>\n

putting eq2 –> eq1<\/span><\/span><\/p>\n

T(n) = T(n-2)*(n-1)<\/span>*n…..eq4<\/span><\/span><\/p>\n

putting eq3 –> eq4<\/span><\/span><\/p>\n

T(n) = T(n-3)*(n-2)<\/span>*(n-1)*n<\/span><\/span><\/p>\n

.<\/span><\/span><\/p>\n

.<\/span><\/span><\/p>\n

T(n) = T(n-k)*(n-(k-1))*……<\/span>*(n-1)*n<\/span><\/span><\/p>\n

putting,<\/span><\/span><\/p>\n

n-k = 1 or<\/span><\/span><\/p>\n

k = n -1<\/span><\/span><\/p>\n

T(n) = T(n-(n-1))*(n-(n-1-1))*……<\/span>*(n-1)*n<\/span><\/span><\/p>\n

T(n) = 1*2*3*……<\/span>*(n-1)*n<\/span><\/span><\/p>\n

T(n) = <\/span>O(n!)<\/span><\/span><\/p>\n

Why? Because, <\/span>1*2*3*……*(n-1)*n = n!<\/span><\/span><\/p>\n

or<\/span><\/span><\/p>\n

T(n) = <\/span>O(n!) <\/span>\u2248  O(n<\/span>n<\/span><\/span>)<\/span><\/span><\/p>\n

Conclusion:<\/span><\/span><\/h2>\n

In substitution method, we mathematically solve the problem. Hence, this method is time consuming, but you need to understand this because sometimes you have a recurrence relation and you need to evaluate the answer using substitution method.<\/span><\/span><\/p>\n

For,<\/span><\/span><\/p>\n

Recursion Tree Method( Iteration Method) <\/span>click here<\/a><\/span>!<\/span><\/span><\/p>\n

Master Theorem <\/span>click here<\/a><\/span>!<\/span><\/span><\/p>\n


<\/span><\/h2>\n
If you find any problem related to this article, please comment below or contact me <\/span>here<\/a><\/span>.<\/span><\/span><\/div>\n

<\/span><\/p>\n

<\/span><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Recurrence Relation: A recurrence relation is a equation or inequality that express a function in terms of its value on a smaller input. How to solve these recurrences? any idea? So, there are three ways to solve the recurrence relations. 1. Substitution Method 2. Recursion Tree Method (Iteration Method) 3.…<\/p>\n

Read the postRecurrence Relation | Substitution Method | BitsOfCS<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3177","post","type-post","status-publish","format-standard","hentry","category-infinity-fitness","excerpt","zoom","full-without-featured","even","excerpt-0"],"yoast_head":"\nRecurrence Relation | Substitution Method | BitsOfCS | ManOrInfinity<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Recurrence Relation | Substitution Method | BitsOfCS\" \/>\n<meta property=\"og:description\" content=\"Recurrence Relation: A recurrence relation is a equation or inequality that express a function in terms of its value on a smaller input. How to solve these recurrences? any idea? So, there are three ways to solve the recurrence relations. 1. Substitution Method 2. Recursion Tree Method (Iteration Method) 3.…\" \/>\n<meta property=\"og:url\" content=\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\" \/>\n<meta property=\"og:site_name\" content=\"ManOrInfinity\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-09T18:51:00+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000\" \/>\n<meta name=\"author\" content=\"manorinfinity\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@manorinfinity\" \/>\n<meta name=\"twitter:site\" content=\"@manorinfinity\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"manorinfinity\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\"},\"author\":{\"name\":\"manorinfinity\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"headline\":\"Recurrence Relation | Substitution Method | BitsOfCS\",\"datePublished\":\"2021-06-09T18:51:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\"},\"wordCount\":547,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"image\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000\",\"articleSection\":[\"Infinity Fitness\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\",\"url\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\",\"name\":\"Recurrence Relation | Substitution Method | BitsOfCS | ManOrInfinity\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000\",\"datePublished\":\"2021-06-09T18:51:00+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage\",\"url\":\"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000\",\"contentUrl\":\"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/manorinfinity.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Recurrence Relation | Substitution Method | BitsOfCS\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#website\",\"url\":\"https:\/\/manorinfinity.com\/blog\/\",\"name\":\"ManOrInfinity\",\"description\":\"Thrive towards greatness\",\"publisher\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/manorinfinity.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\",\"name\":\"manorinfinity\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png\",\"contentUrl\":\"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png\",\"width\":282,\"height\":260,\"caption\":\"manorinfinity\"},\"logo\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/\"},\"description\":\"Complex Problem Solver, Outloud Thinker, An Outstanding Writer, and a very curious human being\",\"sameAs\":[\"http:\/\/manorinfinity.com\"],\"url\":\"https:\/\/manorinfinity.com\/blog\/author\/manorinfinity\/\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Recurrence Relation | Substitution Method | BitsOfCS | ManOrInfinity","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/","og_locale":"en_US","og_type":"article","og_title":"Recurrence Relation | Substitution Method | BitsOfCS","og_description":"Recurrence Relation: A recurrence relation is a equation or inequality that express a function in terms of its value on a smaller input. How to solve these recurrences? any idea? So, there are three ways to solve the recurrence relations. 1. Substitution Method 2. Recursion Tree Method (Iteration Method) 3.…","og_url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/","og_site_name":"ManOrInfinity","article_published_time":"2021-06-09T18:51:00+00:00","og_image":[{"url":"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000","type":"","width":"","height":""}],"author":"manorinfinity","twitter_card":"summary_large_image","twitter_creator":"@manorinfinity","twitter_site":"@manorinfinity","twitter_misc":{"Written by":"manorinfinity","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#article","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/"},"author":{"name":"manorinfinity","@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"headline":"Recurrence Relation | Substitution Method | BitsOfCS","datePublished":"2021-06-09T18:51:00+00:00","mainEntityOfPage":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/"},"wordCount":547,"commentCount":0,"publisher":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"image":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage"},"thumbnailUrl":"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000","articleSection":["Infinity Fitness"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/","url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/","name":"Recurrence Relation | Substitution Method | BitsOfCS | ManOrInfinity","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage"},"image":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage"},"thumbnailUrl":"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000","datePublished":"2021-06-09T18:51:00+00:00","breadcrumb":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#primaryimage","url":"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000","contentUrl":"https:\/\/lh3.googleusercontent.com\/fJOt5QRXQ5sJLI03laYJbNo1--yHTjY-vGpPFsQdep_MMQB31qaVzafoPJhTckKaUI8sItDZoH1RyLa_gC0eH-EKVWtPB-n-I8S8CqUhnT_Nt7SRX0E1Im07onkk1nQVt4J_3xa8=s16000"},{"@type":"BreadcrumbList","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-substitution-method-bitsofcs\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/manorinfinity.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Recurrence Relation | Substitution Method | BitsOfCS"}]},{"@type":"WebSite","@id":"https:\/\/manorinfinity.com\/blog\/#website","url":"https:\/\/manorinfinity.com\/blog\/","name":"ManOrInfinity","description":"Thrive towards greatness","publisher":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/manorinfinity.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901","name":"manorinfinity","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/","url":"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png","contentUrl":"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png","width":282,"height":260,"caption":"manorinfinity"},"logo":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/"},"description":"Complex Problem Solver, Outloud Thinker, An Outstanding Writer, and a very curious human being","sameAs":["http:\/\/manorinfinity.com"],"url":"https:\/\/manorinfinity.com\/blog\/author\/manorinfinity\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts\/3177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/comments?post=3177"}],"version-history":[{"count":0,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts\/3177\/revisions"}],"wp:attachment":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/media?parent=3177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/categories?post=3177"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/tags?post=3177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}