Better Search Performance
Performance
What is the worst case time complexity of Binary Search?
Binary Search(a[1, . . . ,N], k)
Cost Executions
l = 1, r = N + 1 c1 1
while l < r c2 ?? m = l + (r-l) / 2 c3 ?? if (k == a[m]) c4 ?? return True c5 0 else if (k < a[m]) c6 ?? r = m c7 ?? else l = m + 1 c8 ?? return False c9 1 Intuition: loop executes log2N times. Algorithms (580) Introduction January 2018 17 / 28 Better Search Performance Performance Alternative: analyse the recursive form of the program. BinSearch(a, l , r , k) Cost if (l >= r) c1
return False c2
m = l + (r-l) / 2 c3
if (k == a[m]) c4
return True c5
else if (k < a[m]) c6 return BinSearch(a, l, m, k) T(N’) else return BinSearch(a, m+1, r, k) T(N’’) where N ′ and N ′′ are numbers left to search Exercise: what are N ′ and N ′′ in the worst case? Be exact. Algorithms (580) Introduction January 2018 18 / 28 Better Search Performance Worst Case Recursion m is always placed at l + bN/2c if N is odd: N ′ = N ′′ = bN/2c if N is even: N ′ = bN/2c, N ′′ = bN/2c − 1 So the worst case is when k < a[0] If N > 0, will have bN/2c unsearched elements
Algorithms (580) Introduction January 2018 19 / 28
Better Search Recurrence in Binary Search
Performance
We can now write a recursive worst case formula for T (N)
BinSearch(a, l , r , k)
Cost
if (l >= r) c1
return False c2
m = l + (r-l) / 2 c3
if (k == a[m]) c4
return True c5
else if (k < a[m]) c6 return BinSearch(a, l, m, k) T(floor(N/2)) else return BinSearch(a, m+1, r, k) <= T(floor(N/2)) Algorithms (580) Introduction January 2018 20 / 28 Divide and Conquer Time Divide and Conquer Binary Search is a divide and conquer algorithm The overall problem is divided into smaller subproblems Subproblems must be solved The solutions may need to be combined General form of time complexity is expressed recursively: T (N) = { Θ(1) , N < c aT (N/b) + D(N) + C (N) , otherwise where c is some small positive integer, a is number of subproblems, N/b is size of a subproblem, D(N) is cost of division and C (N) is cost of combination. The “otherwise” formula is a recurrence Algorithms (580) Introduction January 2018 21 / 28 Divide and Conquer Time Performance Question What are a, b, c , D(N) and C (N) for Binary Search? BinSearch(a, l , r , k) Cost if (l >= r) c1
return False c2
m = l + (r-l) / 2 c3
if (k == a[m]) c4
return True c5
else if (k < a[m]) c6 return BinSearch(a, l, m, k) T(floor(N/2)) else return BinSearch(a, m+1, r, k) <= T(floor(N/2)) Algorithms (580) Introduction January 2018 22 / 28 Divide and Conquer Time Performance For Binary Search we have T (N) = { c1 + c2 , if N = 0 c1 + c3 + c4 + c6 + T (bN/2c) , if N > 0
or
T (N) =
{
Θ(1) , if N = 0
T (bN/2c) + Θ(1) , if N > 0
Still need to solve the recurrence
Either: guess answer and prove by induction (beyond this course)
Or: apply the master method
Algorithms (580) Introduction January 2018 23 / 28
Divide and Conquer Time
The Master Method
The outcome of the master method is determined by which of
the work to solve the base cases: Θ(N logb a)
the work to divide and recombine at the top level: Θ(f (N))
(note N logb a is how many base cases, each one is Θ(1))
is (strictly) polynomially larger.
If the base case work is larger then T (N) = Θ(N logb a)
If neither is larger, then T (N) = Θ(N logb a logk+12 N)
If the divide and combine work is larger, then T (N) = Θ(f (N))
Look Out!!!
Polynomially larger is not the same as asymptotically larger. So
N log2N 6= Ω(Nc) for any c > 1.
Algorithms (580) Introduction January 2018 24 / 28
Divide and Conquer Master Method
The Master Method [Bentley, Haken, Saxe 1980]
Theorem (Master theorem)
Let a and b be positive real numbers with a ≥ 1 and b > 1. Let f (N) be a
function and let T (N) be defined on the non-negative integers by the
recurrence:
T (N) = aT (N/b) + f (N)
where N/b can be replaced by either bN/bc or dN/be. Then T (N) has
the following asymptotic bounds:
1 If f (N) = O(Nc) and c < logb a, then T (N) = Θ(N logb a) 2 If f (N) = Θ(N logb a logk2 N) then T (N) = Θ(N logb a logk+12 N) for k ≥ 0 3 If f (N) = Ω(Nc), and c > logb a, and af (N/b) ≤ cf (N) for some
c < 1 and all sufficiently large N, then T (N) = Θ(f (N)).
Algorithms (580) Introduction January 2018 25 / 28
Divide and Conquer Master Method
Performance
For Binary Search (worst case)
T (N) = T (bN/2c) + Θ(1)
So, N logb a = N log2 1 = N0 = 1, and therefore
f (N) = Θ(N logb a)
and Case 2, with k = 0, applies.
T (N) = Θ(log2N)
The master method confirms the informal result.
Algorithms (580) Introduction January 2018 26 / 28
Divide and Conquer Master Method
Master Method Case 3
The conditions for Case 3 include an extra check:
af (N/b) ≤ cf (N), where c < 1 for all N > N0
This is the so-called regularity condition. It confirms that the divide and
combine work decreases as the recursion proceeds. If this is not true the
the master theorem does not apply. e.g. for this f (N) there is no N
beyond which f (N) > f (N/2)
Algorithms (580) Introduction January 2018 27 / 28
Divide and Conquer Master Method
Other Excluded Cases
The master method does not apply to these recurrences
T (N) = NT (N/2) + N
T (N) = 0.5T (N/2) + 4N
T (N) = 4T (N/8)− N2
T (N) = 2T (N/2) + N/ logN
The (mostly straightfoward) reasons are
the number of subproblems in the first two
negative divide and combine time (third example)
negative value of k (fourth example)
Algorithms (580) Introduction January 2018 28 / 28