CSC373 Fall’20 Tutorial 1 Tuesday, Sept. 15, 2020
Master Theorem (General Version):
For constants a 1 and b > 1, and an asymptotically positive function f(n), the recurrence relation T (n) a · T (n/b) + O(f (n)) has the following solution.
1. If f(n) = Onlogb a−ε for some constant ε > 0, then T(n) = Onlogb a.
2. If f(n) = Θnlogb a logk n for some constant k 0, then T(n) = Onlogb a logk+1 n.
3. If f(n) = Ωnlogb a+ε for some constant ε > 0 and f satisfies the regularity condition*, then T(n) = O (f(n)).
(*Regularity condition: For some constant c < 1 and all sufficiently large n, a·f (n/b) c·f (n).)
Note: There are recurrence relations which do not fall under any of these three cases (e.g. the recurrence relation T (n) T (n/5) + T (7n/10) + O(n) from QuickSelect where the smaller instances are not of uniform size, or the recurrence relation T (n) √n · T (√n) + O(n) where a and b are not constants). If you’re interested in how more general recurrences can be solved, there are some excellent resources available online.1,2
Q1 Practicing Recurrence Relations
Find the best possible asymptotic upper bound for T(n) under the following recurrence relations.3 (a) T(n)3·T(n/2)+O(nlog3n)
(b) T(n)4·T(n/2)+O(n2)
(c) T(n)2·T(n/2)+O(nlog2n)
(d) T(n)2·T(n/4)+O(n0.5001) Solution to Q1
(a) For T (n) 3T (n/2) + O(n log3 n), we have: a=3andb=2;thus,nlogba =nlog23.
f(n) = nlog3 n.
Hence, by case 1 of the Master theorem, T(n) = O(nlog2 3).
1http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
2 http://web.csulb.edu/~tebert/teaching/lectures/528/recurrence/recurrence.pdf
3Note that when proving an upper bound on the worst-case running time of an algorithm, you would encounter
equations of the form T(n) ... rather than T(n) = ..., yielding T(n) = O(·) rather than T(n) = Θ(·). For a lower bound, you would need to explicitly construct instances on which the algorithm takes the desired amount of time.
1
(b) For T (n) 4T (n/2) + O(n2), we have:
a=4andb=2;thus,nlogba =nlog24 =n2. f(n)=n2.
Hence, by case 2 of the Master theorem, T (n) = O(n2 log n).
(c) For T (n) 2T (n/2) + O(n log2 n), we have a=2andb=2;thus,nlogba =nlog22 =n. f(n) = nlog2 n.
Hence, again by case 2 of the Master theorem, T (n) = O(n log3 n).
(d) For T (n) 2T (n/4) + O(n0.5001), we have
a=2andb=4;thus,nlogba =nlog42 =n0.5. f(n) = n0.5001.
Hence, by case 3 of the Master theorem, T(n) = O(n0.5001). Q2 Monotonic Function Evaluation
Consider a monotonously decreasing function f : N → Z (that is, a function defined on natural numbers which takes integer values and satisfies f(i) > f(i + 1) for all i ∈ N). Assuming we can evaluate f at any point i in constant time, we want to find n = min{i ∈ N|f(i) 0} (that is, we want to find the first point where f becomes non-positive). Note that n is not given to us, but we are told that some point i with f(i) 0 exists (i.e. n is well-defined), and we are allowed to express the running time of our algorithm in terms of n.
We can obviously solve the problem in O(n) time by simply evaluating f(1),f(2),f(3),…,f(n). Describe an O(log n) time algorithm.
[Hint: Try to quickly get an estimate of n, and then precisely pinpoint the exact value of n in the range you estimated.]
Solution to Q2
Let k = 1, and while f(k) > 0, double k. In at most ⌈logn⌉ iterations, this will terminate as we will have k n. Let k∗ be the value at which it terminates. Then, we know that k∗/2 < n k∗. We can binary-search n in this range (or for simplicity, in the range 1 . . . k∗), as described by the function FindFirstNonPositive below.
The running time for finding k∗ is O(log n), and the running time for the subsequent binary search is also O(log n). Hence, the overall running time is O(log n).
2
Function FindFirstNonPositive(A[1 . . . r]) If r = 1 then return A[1].
Else:
– Set m ← ⌊r/2⌋
– If A[m] 0 then return FindFirstNonPositive(A[1 . . . m]). – Else, return FindFirstNonPositive(A[(m + 1) . . . r]).
Q3 Maximum Subarray Sum
You are given an array A[1...n], and you are asked to find the maximum subarray sum, that is, the maximum value of jt=i A[t] over all possible (i, j) with 1 i j n. Design an O(n) time divide and conquer algorithm for the problem.
[Hint: Once you divide the array into two equal halves, say A[1...mid] and A[mid+1...n], you will get the maximum subarray sum within each half. What extra information do you need from each half?
If you spend O(n) time in the merge step to calculate this extra information, you will get O(n log n) running time. Can you get your recursive algorithm to return this information instead?]
Solution to Q3
Suppose we have already calculated the maximum subarray sums in the two halves, A[1 . . . mid] and A[mid +1 . . . n]. To find the overall maximum subarray sum, we need a third value: the maximum subarray sum where the subarray overlaps both halves.
Note that this quantity is the sum of two quantities: the maximum suffix sum in the left half (i.e. maximum sum of any A[i . . . mid]) and the maximum prefix sum in the right half (i.e. maximum sum of any A[mid+1...j]).
After recursively calling our algorithm on the two halves, we could spend O(n) time calculating the maximum suffix sum in the left half and the maximum prefix sum in the right half. But as the hint suggests, this will give us T (n) = 2 · T (n/2) + O(n), i.e., T (n) = O(n log n).
Instead, we want our recursive algorithm to return the maximum suffix sum in addition to the max- imum subarray sum, when called on the left half, and return the maximum prefix sum in addition to the maximum subarray sum, when called on the right half.
That means, our algorithm must return three quantities: maximum subarray sum, maximum prefix sum, and maximum suffix sum. Note that the “parent” call must also return these quantities once getting them from the two recursive calls, otherwise it is not a legitimate recursive algorithm.
When thinking along these lines, it becomes clear that to compute the maximum prefix and suffix sums in the entire array, we will also need to know the sum of the left and right halves. Also, in prefix and suffix sums, we need to allow empty prefix and suffix, which plays a key role in the first step of the algorithm below.
3
Function Subarray-Prefix-Suffix-Sum(A[l . . . r])
If r = l, return (A[l], max(A[l], 0), max(A[l], 0), A[l]).
Set mid = ⌊l + r)/2⌋.
[subarrayLeft,prefixLeft,suffixLeft,sumLeft] = Subarray-Prefix-Suffix-Sum(A[l . . . mid])
[subarrayRight,prefixRight,suffixRight,sumRight]=Subarray-Prefix-Suffix-Sum(A[mid+1...r]) subarray = max(subarrayLeft,subarrayRight,suffixLeft+prefixRight)
prefix = max(prefixLeft,sumLeft+prefixRight)
suffix = max(suffixRight,suffixLeft+sumRight)
sum = sumLeft+sumRight
Return (subarray,prefix,suffix,sum)
Note that the worst-case running time of this algorithm is given by T (n) 2 · T (n/2) + O(1), which yields T (n) = O(n).
4