📎

Master theorem

Master theorem for simple, regular recurrence relations

Given recurrence of the form

T(n)=a⋅T(n/b)+O(ndlog⁡(n)e)\small T(n) = a \cdot T(n/b) + O(n^d \log(n)^e)

for constants a,b,d,e\small a,b,d,e and T(1)\small T(1) .

a\small abranching - expansion, proliferation for subproblems

b\small bshrinkage - of subproblem sizes

c\small cthe hidden constant inO(ndlog⁡(n)e)\small O(n^d \log(n)^e)

Closed form solution:

  1. T(n)∈O(nd⋅log⁡(n)e)\small T(n) \in O(n^d \cdot \log(n)^e) if a/bd<1\small a/b^d < 1
  1. T(n)∈O(nd⋅log⁡(n)e+1)\small T(n) \in O(n^d \cdot \log(n)^{e+1}) if a/bd=1\small a/b^d = 1
  1. T(n)∈O(nlog⁡b(a))\small T(n) \in O(n^{\log_b(a)}) if a/bd>1\small a/b^d > 1

Examples of usage: Recursive scan implementation

  • Example 1

    Recursive definition

    W(1)=O(1)\small W(1) = O(1)

    W(n)=W(n/2)+n\small W(n) = W(n/2) + n

    a=1,b=2,d=1,e=0\small a=1,~ b=2,~ d=1,~ e=0

    Case 1 applies → Solution

    W(n)=O(n)\small W(n) = O(n)

  • Example 2

    Recursive definition

    T(1)=O(1)\small T(1) = O(1)

    T(n)=T(n/2)+1\small T(n) = T(n/2)+ 1

    a=1,b=2,d=0,e=0\small a=1,~ b=2,~ d=0,~ e=0

    Case 2 applies → Solution

    T(n)=O(log⁡n)\small T(n) = O(\log n)