Reaves.dev

v0.1.0

built using

Phoenix v1.7.17

@rapscallionreaves Gitlab Posts Notes Talks Showcase About

Solving Recurrences

Stephen M. Reaves

::

 2025-01-09

Quick examples on how to solve recurrence relations using Master's Theorem

Summary

Quick examples on how to solve recurrence relations using Master’s Theorem

Contents

Common Examples

Example 1

T(n)=4T(n2)+O(n) T(n) = 4T\left(\frac{n}{2}\right) + O(n)

T(n)≤4T(n2)+cn \phantom{T(n)} \le 4T\left(\frac{n}{2}\right) + cn

T(n)≤cn+4T(n2) \phantom{T(n)} \le cn + 4T\left(\frac{n}{2}\right)

T(n)≤cn+4(4T(n22+cn2)) \phantom{T(n)} \le cn + 4\left( 4T\left(\frac{n}{2^2} + c\frac{n}{2} \right) \right)

T(n)≤cn(1+42)+42T(n22) \phantom{T(n)} \le cn\left(1 + \frac{4}{2} \right) + 4^2T\left( \frac{n}{2^2} \right)

T(n)≤cn(1+42+(42)2)+43T(n23) \phantom{T(n)} \le cn\left(1 + \frac{4}{2} + \left(\frac{4}{2}\right)^2 \right) + 4^3T\left( \frac{n}{2^3} \right)

T(n)≤cn(1+42+(42)2+⋯+(42)i−1)+4iT(n2i) \phantom{T(n)} \le cn\left(1 + \frac{4}{2} + \left(\frac{4}{2}\right)^2 + \cdots + \left(\frac{4}{2}\right)^{i-1} \right) + 4^iT\left( \frac{n}{2^i} \right)

let i=log⁡2n then n2i=1\text{let } i = \log_2{n} \text{ then } \frac{n}{2^i} = 1

T(n)≤cn(1+42+(42)2+⋯+(42)log⁡2n−1)+4log⁡2nT(1) \phantom{T(n)} \le cn\left(1 + \frac{4}{2} + \left(\frac{4}{2}\right)^2 + \cdots + \left(\frac{4}{2}\right)^{\log_2{n}-1} \right) + 4^{\log_2{n}}T\left( 1 \right)

T(n)≤O(n)(O((42)log⁡2n))+O(n2) \phantom{T(n)} \le O(n)\left(O\left(\left(\frac{4}{2}\right)^{\log_2{n}}\right)\right) + O\left(n^2\right)

T(n)≤O(n)(O(n2n))+O(n2) \phantom{T(n)} \le O(n)\left(O\left(\frac{n^2}{n}\right)\right) + O\left(n^2\right)

T(n)=O(n)×O(n)+O(n2) \phantom{T(n)} = O(n) \times O(n) + O\left(n^2\right)

T(n)=O(n2) \phantom{T(n)} = O\left(n^2\right)

Geometric Series

For constant α>0 \alpha > 0

∑j=0kαj=1+α+α2+⋯+αk \displaystyle\sum_{j=0}^{k} \alpha^j = 1 + \alpha + \alpha^2 + \cdots + \alpha^k

∑j=0kαj={O(αk)if α>1O(k)if α=1O(1)if α<1 \phantom{\displaystyle\sum_{j=0}^{k} \alpha^j} = \begin{cases} O\left(\alpha^k\right) & \text{if } \alpha > 1 \ O\left(k\right) & \text{if } \alpha = 1 \ O\left(1\right) & \text{if } \alpha < 1 \end{cases}

Manipulating Polynomials

3log⁡2n=nc 3^{\log_2{n}} = n^c

3=2log23 3 = 2^{log_2{3}}

3log⁡2n=(2log23)log⁡2n 3^{\log_2{n}} = \left(2^{log_2{3}}\right)^{\log_2{n}}

3log⁡2n=2log23×log⁡2n \phantom{3^{\log_2{n}}} = 2^{log_2{3} \times \log_2{n}}

3log⁡2n=(2log2n)log⁡23 \phantom{3^{\log_2{n}}} = \left(2^{log_2{n}}\right)^{\log_2{3}}

3log⁡2n=nlog⁡23 \phantom{3^{\log_2{n}}} = n^{\log_2{3}}

Example 2

T(n)=3T(n2)+O(n) T(n) = 3T\left(\frac{n}{2}\right) + O(n)

T(n)≤cn(1+32+(32)2+⋯+(32)i−1)+3iT(n2i) \phantom{T(n)} \le cn\left(1 + \frac{3}{2} + \left(\frac{3}{2}\right)^2 + \cdots + \left(\frac{3}{2}\right)^{i-1} \right) + 3^iT\left( \frac{n}{2^i} \right)

let i=log⁡2n then n2i=1\text{let } i = \log_2{n} \text{ then } \frac{n}{2^i} = 1

T(n)≤cn(1+32+(32)2+⋯+(32)log⁡2n−1)+3log⁡2nT(1) \phantom{T(n)} \le cn\left(1 + \frac{3}{2} + \left(\frac{3}{2}\right)^2 + \cdots + \left(\frac{3}{2}\right)^{\log_2{n}-1} \right) + 3^{\log_2{n}}T\left( 1 \right)

T(n)≤O(n)(O((32)log⁡2n))+3log2n \phantom{T(n)} \le O(n)\left(O\left(\left(\frac{3}{2}\right)^{\log_2{n}}\right)\right) + 3^{log_2{n}}

T(n)≤O(n)(O(3log2n2log2n))+3log2n \phantom{T(n)} \le O(n)\left(O\left( \frac{3^{log_2{n}}}{2^{log_2{n}}} \right)\right) + 3^{log_2{n}}

T(n)≤O(n)(O(3log2nn))+3log2n \phantom{T(n)} \le O(n)\left(O\left( \frac{3^{log_2{n}}}{n} \right)\right) + 3^{log_2{n}}

T(n)≤O(3log2n)+3log2n \phantom{T(n)} \le O\left( 3^{log_2{n}} \right) + 3^{log_2{n}}

T(n)≤O(3log2n) \phantom{T(n)} \le O\left( 3^{log_2{n}} \right)

T(n)≤O(nlog23) \phantom{T(n)} \le O\left( n^{log_2{3}} \right)

General Recurrence

Constants a>0,b>1, a >0, b>1,

T(n)=aT(nb)+O(n) T(n) = aT\left(\frac{n}{b}\right) + O(n)

T(n)={O(nlogba)if a>bO(nlog⁡n)if a=bO(n)if a<b \phantom{T(n)} = \begin{cases} O\left(n^{log_b{a}}\right) & \text{if } a > b \ O\left(n\log{n}\right) & \text{if } a = b \ O\left(n\right) & \text{if } a < b \end{cases}