复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 01 Algorithm analysis and recurrences

Recurrence for merge sort ⊙(1) fn=1, T(n 27(n/2)+⊙(n)jfn>1

Recurrence for merge sort (1) 1, ( ) 2 ( / 2) ( ) 1. n T n T n if n n if ⎧Θ = = ⎨ ⎩ + Θ >

Recurrence for merge sort ⊙(1) if'n=1 T(n 27(n/2)+⊙(n)jfn>1 Solve T(n)=2T(n/2)+ cn, where c>0 is constant

Recurrence for merge sort (1) 1, ( ) 2 ( / 2) ( ) 1. n T n T n if n n if ⎧Θ = = ⎨ ⎩ + Θ > Solve T( n) = 2 T( n/2) + cn, where c > 0 is constant

Recurrence for merge sort ⊙(1) if'n=1 T(n 27(n/2)+⊙(n)jfn>1 Solve T(n)=2T(n/2)+ cn, where c>0 is constant

Recurrence for merge sort (1) 1, ( ) 2 ( / 2) ( ) 1. n T n T n if n n if ⎧Θ = = ⎨ ⎩ + Θ > Solve T( n) = 2 T( n/2) + cn, where c > 0 is constant. T( n )

Recurrence for merge sort ⊙(1) if'n=1 T(n 27(n/2)+⊙(n)jfn>1 Solve T(n)=2T(n/2)+ cn, where c>0 is constant cn T(cn/2) 7(cm/2)

Recurrence for merge sort (1) 1, ( ) 2 ( / 2) ( ) 1. n T n T n if n n if ⎧Θ = = ⎨ ⎩ + Θ > Solve T( n) = 2 T( n/2) + cn, where c > 0 is constant. cn T(cn/2) T(cn/2)

Recurrence for merge sort ⊙(1) if'n=1 T(n 27(n/2)+⊙(n)jfn>1 Solve T(n)=2T(n/2)+ cn, where c>0 is constant cn cn/2 cn/2 cni 7(cn/4)(cm/4)(cm/4

Recurrence for merge sort (1) 1, ( ) 2 ( / 2) ( ) 1. n T n T n if n n if ⎧Θ = = ⎨ ⎩ + Θ > Solve T( n) = 2 T( n/2) + cn, where c > 0 is constant. cn cn/2 cn/2 T(cn/4) T(cn/4) T(cn/4) T(cn/4)