Data Structure Lecture Note (Week 1, Lecture 3)

Recursion

Master Theorem

($b\ge 1$b≥1)

Suppose $F(N) = aF(\frac{N}{b}) + N^c$F(N)=aF(bN​)+Nc, let $c_0 = \log_b a$c0​=logb​a, then:

• $F(N) = \Theta(N^c) $ if $c_0 < c$c0​<c
• $F(N) = \Theta(N^c\log N)$F(N)=Θ(NclogN) if $c_0 = c$c0​=c
• $F(N) = \Theta(N^{c_0})$F(N)=Θ(Nc0​) if $c_0 > c$c0​>c

Proof:

How to calculate $F(N) = aF(\frac{N}{b}) + N^c$F(N)=aF(bN​)+Nc? We need to expand it into recursion and non-recursion parts

That is, $F(N) = N^c [1 + (a/b^c) + (a/b^c)^2+...+(a/b^c)^{\log_b N}]$F(N)=Nc[1+(a/bc)+(a/bc)2+...+(a/bc)logb​N]

If $a/b^c < 1$a/bc<1, the bracket is a convergent geometric sequence, which would finally converge to some real number

If $a/b^c = 1$a/bc=1, we simply add $\log_b N$logb​N times 1

If $a/b^c > 1$a/bc>1, the brackets give $ (1-(a/b^c){\log_bN + 1}) / (1- a/b^c) = \Theta( ((\frac{a}{b^c}) ^{\log_b N}) ) = \Theta(a^{\log_b N} / N^c) = \Theta ( a^{\log_a N / \log_a b } / N^c ) = \Theta (N^{c_0} / N^c) $ , so overall yields $\Theta (N^{c_0})$Θ(Nc0​)

This finished the proof for the Master Theorem.

---

Remark: the reason why it produces at most polynomial complexity is, each time it solves a subproblem with problem size reduced by greater or equal to 1.

Paradigm in Recursion and Pitfalls

Step1: Identify the subproblem

Step2: Solve the origin problem by solving subproblems, then combine the solutions

Or

Step2’: Solve the origin problem by first tackling an easier part, then reduce it to a smaller problem.

---

Pitfall: when you try to use recursion, make sure that

• Subproblems CAN be combined to solve the origin problem. For example, if you are asked to carry a big artifact into the museum, and you think it’s too heavy. You should not try to slice it into small pieces and carry multiple times… Because they cannot be glued OR you do want the artifact intact!
• Subproblems should be ABLE to solved. This means, if the problem have certain constraints, your subproblem must satisfy all the constraints!

---

Examples

Look for a word in a dictionary.

Hanoi Tower Problem (very notorious problem with sole purpose used in academia to train recursion)

Max sum subarray:

​ Input: Array[1,…,n] containing n intergers

​ Output: Compute a subarray A[$i^*$i∗, …, $j^* $] with maximum sum.