Formula Sheets: Divide & Conquer

 Page 1


Divide and Conquer
General Concepts
Recurrence Relation
• General F orm: T(n) = aT(n/b)+f(n) , where a is n um b er of subproblems, n/b is subproblem size,
f(n) is cost of divide and com bine.
Master Theorem
• F or T(n) =aT(n/b)+f(n) , where a= 1 , b> 1 :
– Case 1: If f(n) =O(n
log
b
a-?
) for ?> 0 , then T(n) = T(n
log
b
a
) .
– Case 2: If f(n) = T(n
log
b
a
log
k
n) , then T(n) = T(n
log
b
a
log
k+1
n) .
– Case 3: If f(n) = ?(n
log
b
a+?
) and af(n/b)=cf(n) for c< 1 , then T(n) = T(f(n)) .
Key Algorithms
Binary Searc h
• Recurrence: T(n) =T(n/2)+O(1) .
• Time Complexit y: O(logn) .
• Space Complexit y: O(1) iterativ e, O(logn) recursiv e (stac k).
Merge Sort
• Recurrence: T(n) = 2T(n/2)+O(n) .
• Time Complexit y: O(nlogn) (b est, a v erage, w orst).
• Space Complexit y: O(n) auxiliary .
Quic k Sort
• Recurrence: T(n) =T(k)+T(n-k-1)+O(n) , where k is piv ot p osition.
• Time Complexit y:
– A v erage: O(nlogn) .
– W orst: O(n
2
) (sorted arra y , p o or piv ot).
• Space Complexit y: O(logn) a v erage, O(n) w orst (recursion stac k).
Strassen’s Matrix Mult iplication
• Recurrence: T(n) = 7T(n/2)+O(n
2
) .
• Time Complexit y: O(n
log
2
7
)˜O(n
2.807
) .
• Space Complexit y: O(n
2
) .
Closest P air of P oin ts
• Recurrence: T(n) = 2T(n/2)+O(n) .
• Time Complexit y: O(nlogn) .
• Space Complexit y: O(n) .
Coun t In v ersions in Arra y
• Recurrence: T(n) = 2T(n/2)+O(n) .
• Time Complexit y: O(nlogn) (mo dified Merge Sort).
• Space Complexit y: O(n) .
K-th Smallest/Largest Elem en t
1
Page 2


Divide and Conquer
General Concepts
Recurrence Relation
• General F orm: T(n) = aT(n/b)+f(n) , where a is n um b er of subproblems, n/b is subproblem size,
f(n) is cost of divide and com bine.
Master Theorem
• F or T(n) =aT(n/b)+f(n) , where a= 1 , b> 1 :
– Case 1: If f(n) =O(n
log
b
a-?
) for ?> 0 , then T(n) = T(n
log
b
a
) .
– Case 2: If f(n) = T(n
log
b
a
log
k
n) , then T(n) = T(n
log
b
a
log
k+1
n) .
– Case 3: If f(n) = ?(n
log
b
a+?
) and af(n/b)=cf(n) for c< 1 , then T(n) = T(f(n)) .
Key Algorithms
Binary Searc h
• Recurrence: T(n) =T(n/2)+O(1) .
• Time Complexit y: O(logn) .
• Space Complexit y: O(1) iterativ e, O(logn) recursiv e (stac k).
Merge Sort
• Recurrence: T(n) = 2T(n/2)+O(n) .
• Time Complexit y: O(nlogn) (b est, a v erage, w orst).
• Space Complexit y: O(n) auxiliary .
Quic k Sort
• Recurrence: T(n) =T(k)+T(n-k-1)+O(n) , where k is piv ot p osition.
• Time Complexit y:
– A v erage: O(nlogn) .
– W orst: O(n
2
) (sorted arra y , p o or piv ot).
• Space Complexit y: O(logn) a v erage, O(n) w orst (recursion stac k).
Strassen’s Matrix Mult iplication
• Recurrence: T(n) = 7T(n/2)+O(n
2
) .
• Time Complexit y: O(n
log
2
7
)˜O(n
2.807
) .
• Space Complexit y: O(n
2
) .
Closest P air of P oin ts
• Recurrence: T(n) = 2T(n/2)+O(n) .
• Time Complexit y: O(nlogn) .
• Space Complexit y: O(n) .
Coun t In v ersions in Arra y
• Recurrence: T(n) = 2T(n/2)+O(n) .
• Time Complexit y: O(nlogn) (mo dified Merge Sort).
• Space Complexit y: O(n) .
K-th Smallest/Largest Elem en t
1
• Quic kSelect Recurrence: T(n) =T(n/2)+O(n) a v erage.
• T ime Complexit y:
– A v erage: O(n) .
– W orst: O(n
2
) .
• Space C omplexit y: O(1) iterativ e, O(logn) recursiv e.
K-th El emen t of T w o Sorted Arra ys
• Rec urrence: T(n) =T(n/2)+O(1) (binary searc h on smaller arra y).
• Time Complexit y: O(log(min(m,n))) , where m,n are arra y lengths.
• Space C omplexit y: O(1) iterativ e, O(log(min(m,n))) recursiv e.
2