CS 124 Section 0 Solutions 01/28/2021 Problem 1
In these solutions, I am assuming that we are sorting an array of n distinct elements. Note that the problem should have specified this fact, as an array with repeating elements has a different probability of being sorted.
Let Ai be the event that bogosort finds the correct solution on the 4th shuffle. We are interested in P(A4) = P(Ac1 ∧Ac2 ∧Ac3 ∧A4) = (1−P(A1))(1−P(A2))(1−P(A3))P(A4). For any i, P(Ai) = 1/n! because there are n! possible arrangements of the n elements in an array and only one of these
arrangements is the sorted one. Thus, P(A4) =
Let E(T(n)) be the expected1 number of comparisons necessary to sort an array of n elements. E(T(n)) = E(2T(n/2) + n ∗ n!) = 2E(T(n/2)) + n ∗ n! for n > 1 and 0 otherwise. The closed form solution to this recurrence is
. Let’s prove its correctness.
Proof. I will prove that E(T (n)) = log n n(n/2i)! by induction.
(a) Base case: n = 1. E(T (1)) = 1 ∗ 1! by plugging 1 into the recurrence. log 1(1)(1/2i)! = 1 so 0
the statement holds for n = 1.
(b) Inductive hypothesis: Assume that E(T (k)) = log k k(k/2i)! for all k < n.
(c) Inductive step: Show that the statement holds for k = n. T (n) = 2T (n/2) + n ∗ n! by the given recurrence relation. T(n/2) = log(n/2) n/2(n/2i+1)! by the inductive hypothesis. Plugging
this in, we see that T(n) = n∗n!+log(n/2)n(n/2i+1)! = n∗n!+lognn∗(n/2i)! = 01
log n n(n/2i)! and the statement is true by the principle of mathematical induction. 0
You may be wondering why the hint is correct. Let T be a random variable that represents number of comparisions2 necessary for bogosort to sort an array of n elements. Let I be a random variable that represents the number of iterations necessary to finish sorting the array. Each iteration of bogosort takes n comparisons (shuffling the array and checking if it is sorted), so T = nI. We are interested in E(T) = E(nI). By linearity of expectation, E(nI) = nE(I) (since n is a constant, not a random variable).
E(I) = 1 ∗ 1/n! + (1 + E(I))(1 − 1/n!). If the first iteration succeeds, then E(I) = 1, and this event occurs with probability 1/n!. If the first iteraton fails, then we need 1 + E(I) more
1Note that I say expected because bogosort is a randomized algorithm and may require a different number of iterations each time it is called. We will explore randomized algorithms towards the end of this course.
2The shuffle step in bogosort actually does more than just comparing integers. This quantity really represents the number of “basic steps" that bogosort takes, where a “basic step" is a constant-time operation.
0
0
(1 − 1/n!)31/n!
log n
E(T (n)) = n(n/2i)!
0
0
1
iterations because we are back at square one (bogosort’s future behavior is independent of its past behavior3). This occurs with probability 1 − 1/n!. From here, algebra will show that E(I) = n!, so E(T)=nE(I)=n∗n!. 4
3If you’ve taken Stat 110, this is known as the memoryless property of the geometric distribution.
4If you want an alternate proof of this fact, recognize that I is a geometric random variable. The proof for expectation of a geometric random variable can be found in Chapter 4 of this textbook.
2
Problem 2
Proof. I will show that the closed form solution of the given recurrence is O(n log n) by induction.
(a) Base case: n = 1. T(n) = c ∗ n by the recurrence relation for mergesort. c = 1log1 + 1 =
O(n log n) so the statement is true for n = 1.
(b) Inductive hypothesis: Assume that T (k) = O(k log k) for all k < n.
(c) Inductive step: I will show that T (n) = O(n log n). Using the recurrence for mergesort, T (n) = 2T (n/2) + cn. The inductive hypothesis gives us that T (n/2) = O(n/2 log(n/2)). By the definition of big-O, ∃N, a such that ∀n > N , T (n/2) ≤ a ∗ n/2 log(n/2).
Plugging this in, we get that T(n) ≤ anlog(n/2)+cn = an(logn−1)+cn = anlogn−an+cn. Since this inequality holds for all n > N , T (n) = O(n log n) by the definition of big-O. Thus, the statement is true by the principle of mathematical induction.
The general recurrence relation describing the number of comparisons even when n is not a power of two is
T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + n − 1 The closed form solution to this recurrence is
T(n)=n⌈logn⌉−2⌈logn⌉ +1
Notice that this is still O(n log n). To prove the correctness of this recurrence, I recommend a proof
by cases and induction. This was not required for this section.
Proof. I will do a proof by induction. The formula holds for base case n=1. Plugging 1 into the recurrence yields T(1) = T(1) + T(0) + 1 − 1. Plugging 1 into the formula yields 0 = T(0) + 1 − 1, so the statement is true for n = 1.
Assume as the inductive hypothesis that the formula holds true for everything less than n. Now, we want to prove its correctness for n. This requires showing that:
T(n)=n⌈logn⌉−2⌈logn⌉ +1 (1) (a) Case 1: n is even. If n is even, n is an integer so ⌈n⌉ = ⌊n⌋ = n. The recurrence gives us that
2 222
n n n n log⌈n⌉
T(n) = 2T(2)+n−1. By the inductive hypothesis, T(2) = 2(2 log⌈2⌉−2 2 n n log n ⌈log n⌉
+1)+n−1. Thus,T(n)=2(2 log2 −2 2 +1)+n−1=n⌈logn⌉−2 +1. Therefore,theformula
holds if n is even.
(b) Case 2: n-1 is even, n is odd, and (n − 1)/2 is a power of 2. In this case, ⌈ n ⌉ = n−1 + 1 and
n n−1 n+1 n−1 2 2
⌊2⌋ = 2 . Therefore, using the recurrence, T(n) = T( 2 )+T( 2 )+n−1. Now, I can
plug in the inductive hypothesis to get:
3
T (n) = ( n + 1 )⌈log( n + 1 )⌉ − 2⌈log( n+1 )⌉ + n − 1 ⌈log n − 1 ⌉ − 2⌈log n−1 ⌉ + 2 (2) 22
22 22
Because (n − 1)/2 is a power of two, this can be simplified to T(n) = n+1(log(n−1) + 1) −
22
2 2 + 2 log 2 − 2 2 + 2. With some algebra and application of properties of
log( n−1 )+1 n−1 n−1 log n−1
logarithms, this becomes T (n) = n⌈log n⌉ − 2⌈log n⌉ + 1, so the statement holds in this case.
(c) Case 3: n-1 is even, n is odd, and (n − 1)/2 is not a power of 2. Equation 2 still holds, so we can start from there. Because (n − 1)/2 is not a power of 2, ⌈log( n+1 )⌉ = ⌈log n−1 ⌉ =
⌈log n ⌉ = ⌈log(n)⌉ − 1 by properties of the log and ceiling functions. Substituting those into 2
equation 2, we get that T (n) = n+1 ⌈log n⌉ − 2⌈log n⌉ + n−1 ⌈log n⌉ − 2⌈log n⌉ + 2. 22
T(n + 1) = (n + 1)(⌈log (n + 1)⌉ − 1) − 2(⌈log2(n+1)⌉−1)+ 22
(n)(⌈log (n + 1)⌉ − 1) − 2(⌈log2(n+1)⌉−1) + 2 + n 22
T(n + 1) = (n + 1)⌈log2(n + 1)⌉ − 2⌈log2(n+1)⌉ + 1.
Therefore, the formula holds when n+1 is a power of two as well. By the principle of
mathematical induction, we have proved:
T (n) = n⌈log2 n⌉ − 2⌈log2 n⌉ + 1
22
4
Problem 3
(a) Consider f1(n) = n.
Proof. By definition, if f1(2n) = O(f1(n)), then ∃ c and ∃ N such that ∀n > N, f1(2n) < cf1(n). Letc=5andN=1. ∀n>N,f1(2n)=2n<5n=5f1(n)=cf1(n). Therefore, f1(2n) < cf1(n) so f1(2n) = O(f1(n))
(b) Consider f2(n) = nn.
Proof. f2(2n) is not O(f2(n)) iff ∀ c, ∃ N such that ∀n > N, f2(2n) >= f2(n), which implies
that ∀ c, limx→∞ f2(2n) > 0. cf2 (n)
lim f2(2n) = lim (2n)2n n→∞ f2(n) n→∞ cnn
= 1 lim 22nnn = ∞ c n→∞
Therefore, limx→∞ f2(2n) ̸= 0, so f2(2n) is not O(f2(n)) f2 (n)
(c) Proof. Apply the definition of big-O. If f(n) is O(g(n)), then ∃c1 and ∃N1 such that ∀n > N1, f(n) ≤ c1g(n) If g(n) is O(h(n)), then ∃c2 and ∃N2 such that ∀n > N2, g(n) ≤ c2h(n).
Let N = maximumN1,N2. Then, ∀n > N, f(n) ≤ c1g(n) so by substitution, f(n) ≤ c1c2h(n). Therefore, ∃c = c1c2 such that ∀n > N, f(n) ≤ c(h(n)), so f(n) is O(h(n)) by the definition
of O(n).
(d) Here is a counterexample. Consider
n n is even
f (n)
1 nisodd
1 n is even
g(n)
n nisodd
f(n) ̸= O(g(n)). For any constants c and N, ∃n > N such that n is even and n > c. Therefore, f(n) = n > c = cg(n), so f(n) ̸= O(g(n)).
g(n) ̸= O(f(n)). For any constants c and N, ∃n > N such that n is odd and n > c. Therefore, g(n) = n > c = cf(n), so g(n) ̸= O(f(n)).
5