Recurrence Relations, Code Snippets—Monday, February 3/Tuesday, February 4
Readings
• Lecture Notes Chapter 6: Analyzing Runtime of Code Snippets
• Lecture Notes Chapter 7: Divide & Conquer and Recurrence Relations
Problems: Recurrences
Problem 1 [Solve the Following Recurrences]
Solution Set
CIS 121—Data Structures and Algorithms—Spring 2020
Problem 1 a
Solution.
T(n) =
T(n−1)+n n≥1
1 otherwise
Using the method of iteration, we expand T(n) as follows:
Problem 1 b
Assume n is a power of 2.
= T (0) + i i=1
= 1 + n(n + 1) 2
= Θ(n2)
2T ( n ) + n2 T(n) = 2
1
T (n) = T (n − 1) + n
= [T(n−2)+(n−1)]+n
= [[T (n − 3) + (n − 2)] + (n − 1)] + n
.
= T (0) + 1 + 2 + … + (n − 1) + n n
n > 1 otherwise
1
Solution.
We first solve by iteration. First, we may assume that n is some power of 2 such that n = 2k
T(n) = 2T n+n2 2
n n2 2 =22T22+2 +n
n n2 n2 2 =222T23+22 +2+n
.
n k−1 1i
= 2kT k + n2 22
i=0
The recursion bottoms out when n/2k = 1, i.e., k = lg n. Thus, we get
=⇒ k = lg n.
Solution Set
n k−1 1i k + n2
22
i=0
T (n) = 2k T = 2kT
= 2lgnT(1)+2n21− 1 n
=n+2n2 −2n = Θ(n2)
n 1 − ( 1 )k + n2 2
(geometric series) (substituting k = lgn)
2k 1−1 2
Now, let’s consider a different approach—we’ll expand the recurrence using a recursion tree:
On the right side, we can see the total amount of work done at each level of the tree. Our sum becomes immediately apparent without all the initial algebraic soup! Note that the final summation does not include the work done at the leaves, n, but this does not change the Theta bound.
2
Code Snippets
We can apply our knowledge of Big-O and summations to find the run time of a snippet of our code. Besides recursion, nested iteration is where our code’s efficiency will be bottlenecked. We should consider the loop as a summation, and use our knowledge to simplify it from there. Try starting from the innermost loop with fixed bounds and working outwards.
Problems (Code Snippets)
Problem 2
Problem 2 a
Provide a running time analysis of the following loop:
for (int i = 4; i < n; i = i∗i)
for (int j = 2; j < Math.sqrt(i); j = j+j)
System.out. println(”∗”); Solution.
Let x and y be the numbers of iterations that the outer and inner loops run. To get a better sense of how i and j are changing as the code runs, we construct the following table:
Iteration
Value of i
-
Iteration
Value of j
1
221 =4
-
1
2 = 21
2
222 =16
-
2
4 = 22
3
223 = 256
-
3
8 = 23
.
.
-
.
.
x
22x
-
y
2y
We can represent the run time as a summation:
??
1 (1) x=1 y=1
First, solve for the number of iterations of the outer loop (x) (in terms of n):
22x ≈n⇒x≈lglgn (2)
Then, solve for the number of iterations of the inner loop (y) (in terms of i):
2y ≈√i⇒y≈lg√i (3)
Plug in the upper bound of x, y into the recurrence:
√
lglgnlg i
1 (4) x=1 y=1
Note that i is still on the top of the inner summation, now we want to represent i in terms of x, which is the
current variable on the outer loop:
√
lglgnlg 22x
i=22x⇒ 1 (5)
x=1 y=1
3
Solution Set
Simplify the inner summation:
lglgn lglgn lglgn lglgn
√2x
(lg 2 )=
1 2x
1 ̇x x
22 =Θ( 2) (6)
x=1 x=1
2(lg2 )=
x=1
Use the formula ni=0 2i = 2n+1 − 1 to solve 2x
x=1
T(n) = Θ(2lglgn) = Θ(lgn)
Note: In many cases, you can approximate the upper limits of the loops as it won’t affect the Big-O runtime. If you want to be precise, you’d have to use ceilings and floors to get the proper runtime. Sometimes you can also ignore constants, and when you go through the algebra of a problem for the first time it’s not wrong to ignore them, but after you finish you must look back at your solution and see if an extra constant could have mattered. For example, f(n) = 2n and g(n) = 3n are asymptotically equivalent, but f′(n) = 2n and g′(n) = 3n are not.
Problem 2 b
Provide a running time analysis of the following loop. That is, find both Big-O and Big−Ω:
for(int i = 0; i < n; i++)
for (int j = i; j <= n; j++)
for (int k = i; k <= j; k++) sum++;
Solution.
Observe that for fixed values of i, j, the innermost loop runs max{1, j − i + 1} ≤ n + 1 times. For instance, when i = j = 0, the innermost loop evaluates once. When i = 0, j = n, the innermost loop evaluates n + 1 times. The middle loop runs a total number of O(n − i)2 times. Therefore, the entire block of code runs in O(n3).
To find a lower bound on the running time, we consider smaller subsets of values for i, j and lower-bound the running time for the algorithm on these subsets. (A lower bound there would also be a lower bound for the original code’s running time!) Consider the values of i such that 0 ≤ i ≤ n/4 and values of j such that 3n/4 ≤ j ≤ n. For each of the n2/16 possible combinations of these values of i and j, the innermost loop
runs at least n/2 times. Therefore, the running time is at least Ωn2 · n, or equivalently, Ω(n3). 16 2
Alternate Solution for Big-O.
One could solve this using exact sums, but we will leverage some Big-O notation. We know that the innermost loop runs in at most (j − i + 1) time for fixed i, j (see other solution). Therefore the body of the middle loop runs at most c(j − i + 1) times. Therefore, we can express the running time of the code shown as
nn
c(j − i + 1) = O(n3) i=0 j=i
Note: This summation is difficult to compute by hand. Therefore, we need to have other ways of solving these problems (as shown above).
Additional Practice Problems
Problem 3
Assume n is a power of 3.
2T(n)+n n>1
T(n) = 3 1
otherwise
4
Solution Set
Solution.
We solve this by iteration. First, we may assume that n is some power of 3 such that n = 3k T(n) = 2T n+n
=⇒ k = log3 n.
3
= 2 2T n + n + n
32 3 =222Tn+ n+n+n
=2kT( k)+n 33
i=0
The recursion bottoms out when n/3k = 1, i.e., k = log3 n. Thus, we get
.
33 32 3 n k−1 2i
log3 n−12i 1−2log3 n
2log3nT(1)+n i=0
= nlog3 2 + n 3
3 1−2
3log3 n 2log3n
n
Problem 4
You are given the following algorithm for Bubble-Sort:
Algorithm 1 Bubble Sort function Bubble-Sort(A, n)
for i ← 0 to n − 2 do
for j ← 0 to n − i − 2 do
if A[j] > A[j + 1] then swap(A[j], A[j + 1])
end if end for
end for end function
3
log 2 2log3n
=n3 +3n1− log 2
=n 3 +3n−3n = 3n − 2nlog3 2
= Θ(n)
Given some sequence ⟨a1,a2,…,an⟩ in A, we say an inversion has occurred if aj < ai for some i < j. At each iteration, Bubble-Sort checks the array A for an inversion and performs a swap if it finds one. How many swaps does Bubble-Sort perform in the worst-case and in the average-case?
Solution.
It should be fairly obvious that the worst-case scenario for bubble-sort occurs when A contains elements in reverse-sorted order. Let I denote the number of inversions. In this situation, the total number of inversions is the exact number of possible pairs of elements, as each swap removes exactly one inversion:
n Iworst = 2
5
Solution Set
In the average-case scenario, we determine the expected number of inversions in a random array of n ele- ments. Specifically, we consider a random permutation of n distinct elements, ⟨a1, a2, . . . , an⟩.
Let Xij denote an indicator R.V. such that,
Xij = 0
Thus, we have
1
Iaverage = E[I]= =
if ai, aj inverted otherwise
Xij i,j : i
6
Solution Set