{"id":3176,"date":"2021-06-10T00:32:00","date_gmt":"2021-06-09T19:02:00","guid":{"rendered":"https:\/\/manorinfinity.com\/blog\/recurrence-relation-recursion-tree-method-bitsofcs\/"},"modified":"2021-06-10T00:32:00","modified_gmt":"2021-06-09T19:02:00","slug":"recurrence-relation-recursion-tree-method-bitsofcs","status":"publish","type":"post","link":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/","title":{"rendered":"Recurrence Relation | Recursion Tree Method | BitsOfCS"},"content":{"rendered":"<p style=\"text-align: center;\"><span style=\"font-size: large;\"><br \/><\/span><\/p>\n<\/p>\n<p><span><span style=\"font-family: courier; font-size: large;\"><\/p>\n<h1 dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 6pt; margin-top: 24pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline; white-space: pre-wrap;\">Recursion Tree Method (Iteration Method):<\/span><\/h1>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Recursion tree method is a graphical representation of an iteration method, which is the form of a tree where each level nodes are expended. It is useful when the divide and conquer algorithm is used. In recursion tree, each root and child represent the cost of a single problem.<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span><\/span><\/span><\/p>\n<p><a name='more'><\/a><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">Example 1<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&#8211; Solve the following recurrence relation using recursion tree method (iteration method).<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">T(n) = 2T(n\/2) + n<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">Explanation:&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"border: none; display: inline-block; height: 157px; overflow: hidden; width: 227px;\"><img decoding=\"async\" src=\"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000\" style=\"margin-left: 0px; margin-top: 0px;\" \/><\/span><\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">In the above diagram, the recurrence relation divide into two sub problems. Understood? If not, then look at the recursive equation and diagram simultaneously. The diagram showing the actual meaning of the equation.<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Again,<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"border: none; display: inline-block; height: 291px; overflow: hidden; width: 295px;\"><img loading=\"lazy\" decoding=\"async\" height=\"291\" src=\"https:\/\/lh5.googleusercontent.com\/4tX6AxCJHgtLcYdKvjZaTFV4E__CrVXSNlc9TnfiH9PE7uhE2wBnePj24Uq9JGdUGIJkZ4nUrlkTIJ2mDGMXNN0ToqT293FhTgL0fAXSF3SMiuIMdrLpGYVwd3xI0Rt0fBD0Qa63\" style=\"margin-left: 0px; margin-top: 0px;\" width=\"295\" \/><\/span><\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Now again,<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"border: none; display: inline-block; height: 439px; overflow: hidden; width: 602px;\"><img loading=\"lazy\" decoding=\"async\" height=\"439\" src=\"https:\/\/lh4.googleusercontent.com\/OGVhIGPYPV3astFoNDxIG77jWSghOWjYafgDnb-DsG0GY1J2nkb3pNYKH_V1it1nGPsDgFIuyrSDGJOVA54c6b00WqVjgt-AJdp6umekyRueWDiT00oSfglpzXRqpOLRab9tZEpM\" style=\"margin-left: 0px; margin-top: 0px;\" width=\"602\" \/><\/span><\/span><\/p>\n<p><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = n + n + n + &#8230;. + (log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n times)<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Why <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"> times? Because the height of the tree is <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n.<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = n*<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">O(<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">nlog<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n)<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">Example 2<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&#8211; Solve the following recurrence relation using recursion tree method (iteration method).<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">T(n) = 2T(n\/2) + c; n&gt;1<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">T(n) = c; &nbsp; &nbsp; &nbsp; <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"white-space: pre;\">\t<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n=1<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">Explanation:&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Similarly as previous question-<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"border: none; display: inline-block; height: 471px; overflow: hidden; width: 602px;\"><img loading=\"lazy\" decoding=\"async\" height=\"470\" src=\"https:\/\/lh3.googleusercontent.com\/RQ6Okv5BHeqHznpB5cFj_bESGBnVUrHgchZrSz4aDQuIkH0t2ClajPbUMvMyqwcVB16c1p8pOTraaTjGWIKx41MVz-OMCaJZ4VAT0FaFr6oDkARJ6dYhJVj1aniHwT1wTy7-iPgn=w601-h470\" style=\"margin-left: 0px; margin-top: 0px;\" width=\"601\" \/><\/span><\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = c + 2c + 4c + 8c + &#8230; + (log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n times)<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = c[ 1 + 2 + 4 + 8 + &#8230; + (log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n times)]<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Simply solve the G.P. inside the brackets.<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = c[2<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: super;\">log<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: super;\">n<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"> &#8211; 1] &nbsp; &nbsp; [<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">2<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: super;\">log<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: super;\">n<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"> = n<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: super;\">log<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: super;\">2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"> = n]<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = c[n &#8211; 1]<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">O(n)&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">Example 3<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&#8211; Solve the following recurrence relation using recursion tree method (iteration method).<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">T(n) = T(n\/3) + T(2n\/3) + n<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">Explanation:&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">This question is somewhat different from above question. Why?<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Because, in this question, the recurrence relation is divided into two different parts. In the above questions, <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">the recurrence relation is divided into two equal parts.<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Let&#8217;s see how to solve this one-<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-align: center;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"border: none; display: inline-block; height: 351px; overflow: hidden; width: 523px;\"><img decoding=\"async\" src=\"https:\/\/lh5.googleusercontent.com\/5pkYrntxiSAfJhHt5ODlsOkurhJAp0fXprbo24NTFiMs-6KTmDGGjreqjpySrB6NO0WHntAF4S_v-xsJJ1w7XTXr4D-AiLMfQIT5jg6_WUczOfl9lTqXxrG3igKJKL-LkKXIsDR0=s16000\" style=\"margin-left: 0px; margin-top: 0px;\" \/><\/span><\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">It is clear that the height of the tree is not balanced here. The height of the leftmost branch of the tree is <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">and the height of the rightmost branch of the tree is <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">.&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">So, the longest path is rightmost one, and its length is <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">.&nbsp;<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Hence,&nbsp;<\/span><\/p>\n<p><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = n + n + n + &#8230;. + (log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n times)<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Why <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"> times? Because the height of the rightmost tree is <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n.<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = n*<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">log<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">n<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">T(n) = <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">O(<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">nlog<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"vertical-align: sub;\">3\/2<\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">n)<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<span><\/span><\/span><\/p>\n<p><!--more--><\/p>\n<h2 dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 4pt; margin-top: 18pt;\"><span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; text-decoration-line: underline; text-decoration-skip-ink: none; vertical-align: baseline; white-space: pre-wrap;\">Conclusion:<\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">&nbsp;<\/span><\/span><\/h2>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">In recursion tree method, we graphically solve the problem. This method is not time consuming, just make the visuals for your recurrence relation and solve. <\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">For,<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 12pt; margin-top: 12pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Substitution Method <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; text-decoration-skip-ink: none; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"color: black;\"><a href=\"https:\/\/www.bitsofcs.xyz\/2021\/06\/recurrence-relation.html\" target=\"_blank\" rel=\"noopener noreferrer\">click here<\/a><\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">!<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">Master Theorem <\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; text-decoration-skip-ink: none; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"color: black;\"><a href=\"https:\/\/www.bitsofcs.xyz\/2021\/06\/recurrence-relation-master-theorem-examples.html\" target=\"_blank\" rel=\"noopener noreferrer\">click here<\/a><\/span><\/span><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\">!<\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><br \/><\/span><\/p>\n<p dir=\"ltr\" style=\"line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;\"><span style=\"font-variant-east-asian: normal; font-variant-numeric: normal; vertical-align: baseline; white-space: pre-wrap;\"><span style=\"white-space: normal;\">If you find any problem related to this article, please comment below or contact me&nbsp;<\/span><span style=\"color: black; white-space: normal;\"><a href=\"https:\/\/www.bitsofcs.xyz\/p\/contact-me.html\" target=\"_blank\" rel=\"noopener noreferrer\">here<\/a><\/span><span style=\"white-space: normal;\">.<\/span><\/span><\/p>\n<p><\/span><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Recursion Tree Method (Iteration Method): Recursion tree method is a graphical representation of an iteration method, which is the form of a tree where each level nodes are expended. It is useful when the divide and conquer algorithm is used. In recursion tree, each root and child represent the cost<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\">Read the post<span class=\"screen-reader-text\">Recurrence Relation | Recursion Tree 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-3176","post","type-post","status-publish","format-standard","hentry","category-infinity-fitness","excerpt","zoom","full-without-featured","even","excerpt-0"],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v20.12 (Yoast SEO v26.8) - https:\/\/yoast.com\/product\/yoast-seo-premium-wordpress\/ -->\n<title>Recurrence Relation | Recursion Tree 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-recursion-tree-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 | Recursion Tree Method | BitsOfCS\" \/>\n<meta property=\"og:description\" content=\"Recursion Tree Method (Iteration Method): Recursion tree method is a graphical representation of an iteration method, which is the form of a tree where each level nodes are expended. It is useful when the divide and conquer algorithm is used. In recursion tree, each root and child represent the cost\" \/>\n<meta property=\"og:url\" content=\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\" \/>\n<meta property=\"og:site_name\" content=\"ManOrInfinity\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-09T19:02:00+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=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=\"2 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-recursion-tree-method-bitsofcs\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\"},\"author\":{\"name\":\"manorinfinity\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"headline\":\"Recurrence Relation | Recursion Tree Method | BitsOfCS\",\"datePublished\":\"2021-06-09T19:02:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\"},\"wordCount\":438,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"image\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000\",\"articleSection\":[\"Infinity Fitness\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\",\"url\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\",\"name\":\"Recurrence Relation | Recursion Tree Method | BitsOfCS | ManOrInfinity\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000\",\"datePublished\":\"2021-06-09T19:02:00+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage\",\"url\":\"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000\",\"contentUrl\":\"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/manorinfinity.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Recurrence Relation | Recursion Tree 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 | Recursion Tree 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-recursion-tree-method-bitsofcs\/","og_locale":"en_US","og_type":"article","og_title":"Recurrence Relation | Recursion Tree Method | BitsOfCS","og_description":"Recursion Tree Method (Iteration Method): Recursion tree method is a graphical representation of an iteration method, which is the form of a tree where each level nodes are expended. It is useful when the divide and conquer algorithm is used. In recursion tree, each root and child represent the cost","og_url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/","og_site_name":"ManOrInfinity","article_published_time":"2021-06-09T19:02:00+00:00","og_image":[{"url":"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=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":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#article","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/"},"author":{"name":"manorinfinity","@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"headline":"Recurrence Relation | Recursion Tree Method | BitsOfCS","datePublished":"2021-06-09T19:02:00+00:00","mainEntityOfPage":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/"},"wordCount":438,"commentCount":0,"publisher":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"image":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage"},"thumbnailUrl":"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000","articleSection":["Infinity Fitness"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/","url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/","name":"Recurrence Relation | Recursion Tree Method | BitsOfCS | ManOrInfinity","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage"},"image":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage"},"thumbnailUrl":"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000","datePublished":"2021-06-09T19:02:00+00:00","breadcrumb":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#primaryimage","url":"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000","contentUrl":"https:\/\/lh4.googleusercontent.com\/qlhhNu9qBgv_1oCXQL1Wz7hTmqgd2ml4iqKOIeee5mJ1MSt-HlJ93TxNJRqjkKfhCVxhkIG7NfNOpanf1EMUoZgeB1y_5HRUqclDX4gBZ94Sm1kalEcuyaLVZkn97nEfV0fCZ1nX=s16000"},{"@type":"BreadcrumbList","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/10\/recurrence-relation-recursion-tree-method-bitsofcs\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/manorinfinity.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Recurrence Relation | Recursion Tree 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\/3176","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=3176"}],"version-history":[{"count":0,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts\/3176\/revisions"}],"wp:attachment":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/media?parent=3176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/categories?post=3176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/tags?post=3176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}