{"id":3171,"date":"2021-06-14T12:11:00","date_gmt":"2021-06-14T06:41:00","guid":{"rendered":"https:\/\/manorinfinity.com\/blog\/recurrence-relation-master-theorem-examples-bitsofcs\/"},"modified":"2021-06-14T12:11:00","modified_gmt":"2021-06-14T06:41:00","slug":"recurrence-relation-master-theorem-examples-bitsofcs","status":"publish","type":"post","link":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/","title":{"rendered":"Recurrence Relation | Master Theorem | Examples | BitsOfCS"},"content":{"rendered":"

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

<\/p>\n

Master Theorem:<\/span><\/h1>\n

Master Theorem is a cookbook method for determining solutions to recurrence equations of a specific form.<\/span><\/p>\n

<\/p>\n

So, in the first step you should match your recurrence equation with the equation given below and determine the value of some constants (a,b,k and p) then select the appropriate case-<\/span><\/p>\n

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

T(n) = a T(n\/b) + \u0398(n<\/span>k<\/span><\/span> log<\/span>p<\/span><\/span>n)<\/span><\/p>\n

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

Where <\/span>a\u22651<\/span>, <\/span>b>1<\/span>, <\/span>k\u22650<\/span> and <\/span>p\u2208R<\/span>(real numbers). These conditions are important. Why? Because these condition help to check the properties the given constants (<\/span>a, b, k, p<\/span>). That helps to determine the time complexity using Master theorem.<\/span><\/p>\n

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

CASE-1<\/span>: if a > b<\/span>k<\/span><\/span> , then T(n)=\u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span>)<\/span><\/span><\/h2>\n

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

CASE-2<\/span>: if a = b<\/span>k<\/span><\/span> ,<\/span><\/span><\/h2>\n

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

a) <\/span>If p>-1, then <\/span>T(n)=\u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span> log<\/span>p+1<\/span><\/span>n)<\/span><\/p>\n

b) <\/span>If p=-1, then <\/span>T(n)=\u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span> log(logn))<\/span><\/p>\n

c) <\/span>If p<-1, then <\/span>T(n)=\u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span>)<\/span><\/p>\n

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

CASE-3<\/span>: if a < b<\/span>k<\/span><\/span> ,<\/span><\/span><\/h2>\n

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

a) <\/span>If p\u22650, then <\/span>T(n)=\u0398(n<\/span>k<\/span><\/span>log<\/span>p<\/span><\/span>n)<\/span><\/p>\n

b) <\/span>If p<0, then <\/span>T(n)=O(n<\/span>k<\/span><\/span>)<\/span><\/p>\n

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

<\/p>\n

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

Substitution Method<\/span> <\/span>click here<\/a><\/span>!<\/span><\/p>\n

Recursion tree method<\/span> <\/span>click here<\/a><\/span>!<\/span><\/p>\n

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

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

Example-1: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

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

Simply, compared with the above equation given in the Master theorem.<\/span><\/p>\n

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

a=4, b=2, k=2, p=0<\/span><\/p>\n

Now, identifying the matching case-<\/span><\/p>\n

a = b<\/span>k<\/span><\/span><\/p>\n

Why?<\/span><\/span><\/p>\n

a = b<\/span>k<\/span><\/span> => 4 = 2<\/span>2<\/span><\/span> => 4 = 4<\/span><\/p>\n

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

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

Why?<\/span><\/p>\n

Because, p=0<\/span><\/p>\n

Hence, CASE <\/span>2.a<\/span> is applied here!  <\/span><\/p>\n


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

T(n) = \u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span> log<\/span>p+1<\/span><\/span>n)<\/span><\/p>\n

T(n) = \u0398(n<\/span>log<\/span><\/span>2<\/span><\/span>4<\/span><\/span> log<\/span>0+1<\/span><\/span>n)<\/span><\/p>\n

T(n) = <\/span>\u0398(n<\/span>2<\/span><\/span>.logn)<\/span><\/p>\n

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

Example-2: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

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

Simply, compared with the above equation given in the Master theorem.<\/span><\/p>\n

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

a=4, b=2, k=1, p=1<\/span><\/p>\n

Now, identifying the matching case-<\/span><\/p>\n

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

Why?<\/span><\/span><\/p>\n

a > b<\/span>k<\/span><\/span> => 4 > 2<\/span>1<\/span><\/span> => 4 > 2<\/span><\/p>\n

Hence, CASE <\/span>1<\/span> is applied here!  <\/span><\/p>\n


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

T(n) = \u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span>)<\/span><\/p>\n

T(n) = \u0398(n<\/span>log<\/span><\/span>2<\/span><\/span>4<\/span><\/span>)<\/span><\/p>\n

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

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

Example-3: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

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

Simply, compared with the above equation given in the Master theorem.<\/span><\/p>\n

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

a=5, b=3, k=1, p=0<\/span><\/p>\n

Now, identifying the matching case-<\/span><\/p>\n

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

Why?<\/span><\/span><\/p>\n

a > b<\/span>k<\/span><\/span> => 5 > 3<\/span>1<\/span><\/span> => 5 > 3<\/span><\/p>\n

Hence, CASE <\/span>1<\/span> is applied here!  <\/span><\/p>\n


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

T(n) = \u0398(n<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span>)<\/span><\/p>\n

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

T(n) = <\/span>\u0398(n<\/span>log<\/span><\/span>3<\/span><\/span>5<\/span><\/span>)  <\/span><\/p>\n


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

<\/p>\n

Example-4: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

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

Simply, compared with the above equation given in the Master theorem.<\/span><\/p>\n

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

a=4, b=2, k=3, p=0<\/span><\/p>\n

Now, identifying the matching case-<\/span><\/p>\n

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

Why?<\/span><\/span><\/p>\n

a < b<\/span>k<\/span><\/span> => 4 < 2<\/span>3<\/span><\/span> => 4 < 8<\/span><\/p>\n

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

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

Why?<\/span><\/p>\n

Because, p=0<\/span><\/p>\n

Hence, CASE <\/span>3.a<\/span> is applied here!  <\/span><\/p>\n

T(n) = \u0398(n<\/span>3<\/span><\/span>log<\/span>0<\/span><\/span>n)<\/span><\/p>\n

T(n) = <\/span>\u0398(n<\/span>3<\/span><\/span>)<\/span><\/p>\n

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

Example-5: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

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

Here, values of a and k are not constant, so the Master theorem cannot apply here.<\/span><\/p>\n

As, a=3<\/span>n<\/span><\/span> , b=2 , k=n, p=0<\/span><\/p>\n

<\/p>\n

Example-6: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

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

Simply, compared with the above equation given in the Master theorem.<\/span><\/p>\n

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

a=2, b=4, k=0.55, p=0<\/span><\/p>\n

Now, identifying the matching case-<\/span><\/p>\n

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

Why?<\/span><\/span><\/p>\n

a < b<\/span>k<\/span><\/span> => 2 < 4<\/span>0.55<\/span><\/span> => 4<\/span>0.50<\/span><\/span> < 4<\/span>0.55<\/span><\/span><\/p>\n

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

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

Why?<\/span><\/p>\n

Because, p=0<\/span><\/p>\n

Hence, CASE <\/span>3.a<\/span> is applied here!  <\/span><\/p>\n

T(n) = \u0398(n<\/span>0.55<\/span><\/span>log<\/span>0<\/span><\/span>n)<\/span><\/p>\n

T(n) = <\/span>\u0398(n<\/span>0.55<\/span><\/span>)<\/span><\/p>\n

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

Example-7: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

Here, recurrence relation is not valid (as -ve sign is used). So, the Master theorem cannot apply here.<\/span><\/p>\n

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

Example-8: <\/span>Solve the given recurrence using Master theorem-<\/span><\/p>\n

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

Here, recurrence relation is not valid. So, the Master theorem cannot apply here.<\/span><\/p>\n

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

n = 2<\/span>m<\/span><\/span> => m = log<\/span>2<\/span><\/span>n <\/span><\/p>\n

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

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

Now assume, T(2<\/span>m<\/span><\/span>) = S(m)<\/span><\/p>\n

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

S(m) = S(m\/2) + c<\/span><\/p>\n

Now, we can apply Master theorem- <\/span><\/p>\n

a=1, b=2, k=0, p=0<\/span><\/p>\n

<\/p>\n

Now, identifying the matching case-<\/span><\/p>\n

a = b<\/span>k<\/span><\/span><\/p>\n

Why?<\/span><\/span><\/p>\n

a = b<\/span>k<\/span><\/span> => 1 = 2<\/span>0<\/span><\/span> => 1 = 1<\/span><\/p>\n

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

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

Why?<\/span><\/p>\n

Because, p=0<\/span><\/p>\n

Hence, CASE <\/span>2.a<\/span> is applied here!  <\/span><\/p>\n

<\/p>\n

S(m) = \u0398(m<\/span>log<\/span><\/span>b<\/span><\/span>a<\/span><\/span> log<\/span>p+1<\/span><\/span>m)<\/span><\/p>\n

S(m) = \u0398(m<\/span>log<\/span><\/span>2<\/span><\/span>1<\/span><\/span> log<\/span>0+1<\/span><\/span>m)<\/span><\/p>\n

S(m) = \u0398(m<\/span>0<\/span><\/span> log<\/span>1<\/span><\/span>m) <\/span><\/p>\n

S(m) = \u0398(logm)<\/span><\/p>\n

T(2<\/span>m<\/span><\/span>) = \u0398(logm)            <\/span>\t<\/span><\/span>(S(m) = T(2<\/span>m<\/span><\/span>))<\/span><\/p>\n

T(n) =  <\/span>\u0398(log(log<\/span>2<\/span><\/span>n))<\/span>       (n=2<\/span>m<\/span><\/span>)or(m=log<\/span>2<\/span><\/span>n) <\/span><\/p>\n


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

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

<\/span><\/span><\/div>\n

<\/span><\/span><\/div>\n

<\/span><\/span><\/div>\n


<\/span><\/div>\n

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

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

  Master Theorem: Master Theorem is a cookbook method for determining solutions to recurrence equations of a specific form. So, in the first step you should match your recurrence equation with the equation given below and determine the value of some constants (a,b,k and p) then select the appropriate case-<\/p>\n

Read the postRecurrence Relation | Master Theorem | Examples | 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-3171","post","type-post","status-publish","format-standard","hentry","category-infinity-fitness","excerpt","zoom","full-without-featured","even","excerpt-0"],"yoast_head":"\nRecurrence Relation | Master Theorem | Examples | 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\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Recurrence Relation | Master Theorem | Examples | BitsOfCS\" \/>\n<meta property=\"og:description\" content=\"  Master Theorem: Master Theorem is a cookbook method for determining solutions to recurrence equations of a specific form. So, in the first step you should match your recurrence equation with the equation given below and determine the value of some constants (a,b,k and p) then select the appropriate case-\" \/>\n<meta property=\"og:url\" content=\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\" \/>\n<meta property=\"og:site_name\" content=\"ManOrInfinity\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-14T06:41:00+00:00\" \/>\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=\"4 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\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\"},\"author\":{\"name\":\"manorinfinity\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"headline\":\"Recurrence Relation | Master Theorem | Examples | BitsOfCS\",\"datePublished\":\"2021-06-14T06:41:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\"},\"wordCount\":812,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"articleSection\":[\"Infinity Fitness\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\",\"url\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\",\"name\":\"Recurrence Relation | Master Theorem | Examples | BitsOfCS | ManOrInfinity\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#website\"},\"datePublished\":\"2021-06-14T06:41:00+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/manorinfinity.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Recurrence Relation | Master Theorem | Examples | 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 | Master Theorem | Examples | 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\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/","og_locale":"en_US","og_type":"article","og_title":"Recurrence Relation | Master Theorem | Examples | BitsOfCS","og_description":"  Master Theorem: Master Theorem is a cookbook method for determining solutions to recurrence equations of a specific form. So, in the first step you should match your recurrence equation with the equation given below and determine the value of some constants (a,b,k and p) then select the appropriate case-","og_url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/","og_site_name":"ManOrInfinity","article_published_time":"2021-06-14T06:41:00+00:00","author":"manorinfinity","twitter_card":"summary_large_image","twitter_creator":"@manorinfinity","twitter_site":"@manorinfinity","twitter_misc":{"Written by":"manorinfinity","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#article","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/"},"author":{"name":"manorinfinity","@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"headline":"Recurrence Relation | Master Theorem | Examples | BitsOfCS","datePublished":"2021-06-14T06:41:00+00:00","mainEntityOfPage":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/"},"wordCount":812,"commentCount":0,"publisher":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"articleSection":["Infinity Fitness"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/","url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/","name":"Recurrence Relation | Master Theorem | Examples | BitsOfCS | ManOrInfinity","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/#website"},"datePublished":"2021-06-14T06:41:00+00:00","breadcrumb":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/14\/recurrence-relation-master-theorem-examples-bitsofcs\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/manorinfinity.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Recurrence Relation | Master Theorem | Examples | 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\/3171","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=3171"}],"version-history":[{"count":0,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts\/3171\/revisions"}],"wp:attachment":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/media?parent=3171"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/categories?post=3171"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/tags?post=3171"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}