Divide-and-conquer Algorithms

CS 312 - Algorithms - Mount Holyoke College

Divide and conquer�(recursion tree/unrolling)

Reading: Kleinberg & Tardos

Ch. 5.1 and 5.2

Additional resource: CLRS Ch. 4.4

CS 312 - Algorithms - Mount Holyoke College

Golden lion tamarins

Suppose you grew up in the 80s (!) and needed to write a �report on the golden lion tamarin. You go to the library and�find the encyclopedia for “G” with your fingers crossed that�there is an entry for golden lion tamarin. �����

How do you search for the entry quickly?

CS 312 - Algorithms - Mount Holyoke College

Binary search, of course!

binarySearch( searchKey, sorted array A, loIndex, hiIndex ):� if ( hiIndex < loIndex )� return -1� else� midIndex = ( loIndex + hiIndex ) / 2 � if ( A[midIndex] == searchKey )� return midIndex� else if ( searchKey < A[midIndex] )� return binarySearch( searchKey, A, loIndex, midIndex)� else // searchKey > A[midIndex] � return binarySearch( searchKey, A, midIndex, hiIndex)

What is the running time?

CS 312 - Algorithms - Mount Holyoke College

In ye olden days…

Suppose you needed to organize the contact information for your friends, but you don’t have access to any digital devices. You do have a fascinating solution called a “Rolodex” but… you dropped it on the floor, and now the cards are all mixed up!�����

How can you sort your cards efficiently?

CS 312 - Algorithms - Mount Holyoke College

Merge sort, of course!

mergeSort( array A ):� if ( A.length == 1 ) // base case� return� else // recursive case� midIndex = A.length / 2 � leftA = copy( A, 0, midIndex )� mergeSort( leftA ) // recursively sort left half� rightA = copy( A, midIndex + 1, A.length )� mergeSort( rightA ) // recursively sort right half� merge( leftA, rightA, A ) // merge halves back to A�

What is the running time?

CS 312 - Algorithms - Mount Holyoke College

Divide and conquer design technique

• Divide into smaller problems (usually recursively)
• Conquer small problems (base cases)
• Combine solutions to smaller problems (recursive “glueing”)��

How do we analyze the running time?

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation

• Binary search

T(n) = T(n/2) + O(1) T(1) = O(1)

total running time

recursive half-sized call time

overhead for breaking into smaller problem and combining

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation

• Binary search

T(n) = T(n/2) + O(1) T(1) = O(1)

​

​

• Merge sort

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)

​

total running time

recursive half-sized call time

overhead for breaking into smaller problem and combining

total running time

recursive left half call time

overhead for breaking into smaller problem and combining

recursive right half call time

CS 312 - Algorithms - Mount Holyoke College

Solving recurrence relations

• Goal: find closed form (no dependence on T)
• Approaches:
• Recursion tree/unrolling
• [Guess solution & check with induction]
• Unified theorem [when applicable]

• Examples
• Binary search�T(n) = T(n/2) + O(1) T(1) = O(1)�T(n) = O(log n)
• Merge sort�T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)�T(n) = O(n log n)

Fibonacci example

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

​

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

T(n)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

T(n/2)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

T(n/2)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= [T(n/4) + O(1)] + O(1)

​

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

​

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

​

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

= [T(n/8) + O(1)] + O(1) + O(1)

​

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

O(1)

T(n/8)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

= T(n/8) + O(1) + O(1) + O(1)

​

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

O(1)

T(n/8)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

= T(n/8) + O(1) + O(1) + O(1)

…

= O(1) + O(1) + … + O(1)

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

O(1)

O(1)

…

O(1)

tree height is?

# unrollings is?

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

= T(n/8) + O(1) + O(1) + O(1)

…

= O(1) + O(1) + … + O(1)

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

O(1)

O(1)

…

O(1)

O(log n)

height

O(log n) unrollings

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: binary search recurrence

Unrolling

T(n)

= T(n/2) + O(1)

= T(n/4) + O(1) + O(1)

= T(n/8) + O(1) + O(1) + O(1)

…

= O(1) + O(1) + … + O(1)

Recursion tree

​

T(n) = T(n/2) + O(1)�T(1) = O(1)

​

O(1)

O(1)

O(1)

O(1)

…

O(1)

O(log n)*�O(1)

= �O(log n)

O(log n)*O(1) = O(log n)

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation: merge sort

Solve the recurrence relation for merge sort using both the recursion tree and unrolling methods.

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)

When n is even…

T(n) = 2*T(n/2) + O(n) T(1) = O(1)

​

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

​

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

T(n)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

T(n/2)

T(n/2)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

T(n/2)

T(n/2)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

T(n/2)

T(n/2)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*[2T(n/4)+O(n/2)] + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/4)

T(n/4)

T(n/4)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ 2*O(n/2) + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/4)

T(n/4)

T(n/4)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/4)

T(n/4)

T(n/4)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/4)

T(n/4)

T(n/4)

T(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*[2T(n/8) + O(n/4)]+O(n)+O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + 4*O(n/4)+O(n)+O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

T(n/8)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

…

O(1) … O(1)

​

# levels is?

# unrollings is?

O(n/4)

O(n/4)

O(n/4)

O(n/4)

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

O(n/4)

…

O(1) … O(1)

​

# unrollings: log n

​

work at �depth i�?

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

0(n/4)

O(n/4)

O(n/4)

O(n/4)

…

O(1) … O(1)

​

# unrollings: log n

work at �depth i�?

#levels:

1 + log n

depth 0: �1 node

O(n) work

depth 1: �2 nodes

O(n/2)

depth 2: �4 nodes

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

depth 3: �8 nodes

O(n/8)

depth i: �2ⁱ nodes

O(n/(2ⁱ))

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

work at �depth i: 2ⁱ*O(n/2ⁱ)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

work at �depth i:

O(n)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

work at each level: O(n)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

�

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

work at each level: O(n)

total: O(n log n)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

� = (2^{log n})T(0) + (log n)O(n) = O(n log n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

work at each level: O(n)

total: O(n log n)

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recursion tree/unrolling: merge sort recurrence

Unrolling

T(n)

= 2*T(n/2) + O(n)

= 2*2T(n/4)+ O(n) + O(n)

= 2*2*2T(n/8) + O(n)+O(n)+O(n)

…

= 2 * … *2T(0) + O(n) + … + O(n)

� = (2^{log n})T(0) + (log n)O(n) = O(n log n)

Recursion tree

​

T(n) = 2*T(n/2) + O(n)�T(1) = O(1)

​

O(n)

O(n/2)

O(n/2)

…

O(1) … O(1)

​

# unrollings: log n

work at each level: O(n)

total: O(n log n)

# base cases�*base case work

O(n/4)

O(n/4)

O(n/4)

O(n/4)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

O(n/8)

T(n/8)

O(n/8)

O(n/8)

#levels:

1 + log n

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation: merge sort

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)

When n is even…

T(n) = 2*T(n/2) + O(n) T(1) = O(1)

T(n) = O(n log n)

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation: merge sort

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)

When n is even…

T(n) = 2*T(n/2) + O(n) T(1) = O(1)

T(n) = O(n log n)

When n is odd…

T(n) ≤ T(n+1)� T(n) = O((n+1)log(n+1)) �

Aside: log(n+1) = O(log n)

log(n+1) ≤ log(n + n)

log(n+1) ≤ log(2n)

log(n+1) ≤ log(2) + log(n)

log(n+1) ≤ 1 + log(n)

log(n+1) = O(log n)

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation: merge sort

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)

When n is even…

T(n) = 2*T(n/2) + O(n) T(1) = O(1)

T(n) = O(n log n)

When n is odd…

T(n) ≤ T(n+1)� T(n) = O((n+1)log(n)) � T(n) = O(n log n + log n)��

CS 312 - Algorithms - Mount Holyoke College

Recurrence relation: merge sort

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n) T(1) = O(1)

When n is even…

T(n) = 2*T(n/2) + O(n) T(1) = O(1)

T(n) = O(n log n)

When n is odd…

T(n) ≤ T(n+1)� T(n) = O((n+1)log(n)) � T(n) = O(n log n + log n)� T(n) = O( n log n)��

CS 312 - Algorithms - Mount Holyoke College

CS 312 - Algorithms - Mount Holyoke College

Divide and conquer�(unified theorem)

Reading: Kleinberg & Tardos

Ch. 5.2

CLRS Ch. 4.5

CS 312 - Algorithms - Mount Holyoke College

Useful facts

• Geometric sum: when r ≠ 1

�

• Change of base for logs: Log “flipping”:

​

• Exponent “power” rule

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

Consider the general recurrence:

​

assume O(1) base case

CS 312 - Algorithms - Mount Holyoke College

What?

1. We know:

​

​

• So:

CS 312 - Algorithms - Mount Holyoke College

Special case

T(n) = aT(n/b) + n, a > b

​

• How can we start analyzing this?

CS 312 - Algorithms - Mount Holyoke College

Special case: T(n) = aT(n/b) + cn, a > b

This bound counts the "interior nodes", so the leaves must be counted separately.

​

It turns out (since the leaves have a constant size) thatwe could omit the -1 and treat every depth (including the leaves) the same.

CS 312 - Algorithms - Mount Holyoke College

Special case: T(n) = aT(n/b) + cn, a > b

​

Now add the leaf/base case work:

• number of leaves is
• each leaf/base case takes O(1) work
• so total leaf work is

Thus, the total bound is:

c’ > 0 since a > b

CS 312 - Algorithms - Mount Holyoke College

Special case: T(n) = aT(n/b) + cn, a > b

​

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

Consider the general recurrence:

​

assume O(1) base case

• # leaves gives total amount of work done by base cases
• What about work outside of recursive calls?
• How much work is done outside the recursive calls?

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

​

​

​

​

​

​

​

CLRS Figure 4.7

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

Consider the general recurrence:

​

assume O(1) base case

• # leaves gives total amount of work done by base cases
• What about work outside of recursive calls?
• How much work is done at depth i outside the recursive calls?�aⁱ nodes, each node is of size �=>

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

Consider the general recurrence:

​

assume O(1) base case

• # leaves gives total amount of work done by base cases
• What about work outside of recursive calls?
• depth i:��
• Total is:

leaves/base cases

internal nodes - outside recursive calls

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

[CLRS]

CS 312 - Algorithms - Mount Holyoke College

Unified theorem

Compare f(n) with n

1. f(n) smaller, so dominating term is n�Main work is done by "conquering" → leaf work
2. f(n) is the same�Dividing and conquering both contribute to work
3. f(n) is bigger, dominates growth�Main work is done by “dividing” (root)

CS 312 - Algorithms - Mount Holyoke College

Huh?

CS 312 - Algorithms - Mount Holyoke College

Example 1

�T(n) = T(n/2) + d, for some constant d

1. Determine parameter values: a = 1, b = 2, f(n) = d = O(1)
2. Compute log_ba = log₂ 1 = 0
3. Compare f(n) with�Compare O(1) with n⁰=1 → tight bound Θ!
4. f(n) = Θ(1), so we are in case 2
5. Thus, T(n) = Θ(log n)

CS 312 - Algorithms - Mount Holyoke College

Example 2

�T(n) = 9T(n/3) + n

• Determine parameter values: a = 9, b = 3, f(n) = n
• Compute log_ba = log₃ 9 = 2
• Compare f(n) with�Compare n with n²; not tight bound Θ
• f(n) = n = O(n^2-1); letting ϵ = 1 shows that we are in case 1
• Thus, T(n) = Θ(n²)

CS 312 - Algorithms - Mount Holyoke College

Example 3

�T(n) = 3T(n/9) + 2n

• Determine parameter values: a = 3, b = 9, f(n) = 2n
• Compute log_ba = log₉ 3 = .5
• Compare f(n) with�Compare 2n with √n; not tight bound
• Case 3:
1. f(n) = 2n = Ω(n) [let ϵ = .5 > 0]
2. 3 f(n/9) = 3 (2n/9) = 1/3 (2n) ≤ c f(n) [let c = 1/3 < 1]
• Thus, T(n) = Θ(n)

CS 312 - Algorithms - Mount Holyoke College

Example 4

�T(n) = 3T(n/2) + n

• Determine parameter values: a = 3, b = 2, f(n) = n
• Compute log_ba = log₂ 3 = 1.5849….
• Compare f(n) with�Compare n with n^1.585; not tight bound
• Case 1: f(n) = n = O(n) [let ϵ = .5 > 0]
• Thus, T(n) = Θ(n^1.5849...)

CS 312 - Algorithms - Mount Holyoke College