Randomized Algorithm Analysis: Expected vs. Worst-Case Time Complexity ( Data Structures and Algorithms )
A comprehensive solution set for analyzing the time complexity of randomized algorithms. This download includes step-by-step derivations for Worst-Case and Expected Running Time $E[T(n)]$ using probabilistic analysis, summation approximations, and bounds for recursive functions with random variables.
1. (10 points) Consider the following function:
1 function func1(A, n)
2 s ← 0;
3 k ← Random(n);
4 for i0 ← 1 to k do
5 for i1 ← 1 to k do
6 for i2 ← 1 to ⌊
√
k⌋ do
7 s ← s + A[i0] − A[i1] + A[i2];
8 end
9 end
10 end
11 return s
(a) (2 points) What is the asymptotic worst case running time of func1?
(b) (8 points) What is the asymptotic expected running time of func1? Justify your solution with a
complete calculation.
2. (10 points) Consider the following function:
1 function func2(A, n)
2 s ← 0;
3 k ← Random(⌊4 log2
(n)⌋);
4 for i ← 1 to 2
k do
5 s ← s + A[i];
6 end
7 return s
(a) (2 points) What is the asymptotic worst case running time of func2?
1
(b) (8 points) What is the asymptotic expected running time of func2? Justify your solution.
Hint: 2
4 log2
(n) = (2log2
(n)
)
4 = n
4
.
3. (10 points) Consider the following function:
1 function func3(A, n)
2 s ← 0;
3 k ← Random(n);
4 if k ≤ 7 then
5 for i ← n to ⌊n
5/3
⌋ do s ← s + i × A[⌈i/n⌉];
6 else
7 for i ← n to ⌊n log2
(n)⌋ do s ← s + i × A[⌈i/n⌉];
8 end
9 return s
(a) (2 points) What is the asymptotic worst case running time of func3?
(b) (8 points) What is the asymptotic expected running time of func3? Justify your solution.
4. (10 points) Consider the following function:
1 function func4(A, n)
2 s ← 0;
3 k ← Random(n);
4 if k ≤ n
2/3
then
5 for i ← n to ⌊n
5/3
⌋ do s ← s + i × A[⌈i/n⌉];
6 else
7 for i ← n to ⌊n log2
(n)⌋ do s ← s + i × A[⌈i/n⌉];
8 end
9 return s
(a) (2 points) What is the asymptotic worst case running time of func4?
(b) (8 points) What is the asymptotic expected running time of func4? Justify your solution.
5. (15 points) Consider the following recursive function:
1 function func5(A, n)
2 if n ≤ 30 then return A[1];
3 s ← A[1];
4 for i0 ← 1 to ⌊n/2⌋ do
5 for i1 ← 1 to ⌊
√
n⌋ do
6 s ← s + A[i0] × A[i1];
7 end
8 end
9 k1 ← Random(n);
10 k2 ← Random(n);
11 if k1 < 3n/8 then s ← s + func5(A, n − 6);
12 if k2 < 5n/8 then s ← s + func5(A, n − 9);
13 return s
2
(a) (5 points) What is the asymptotic worst case running time of func5? Justify your solution.
(b) (10 points) What is the asymptotic expected running time of func5? Justify your solution.
6. (15 points) Consider the following recursive function:
1 function func6(A, n)
2 if n ≤ 40 then return A[1];
3 s ← A[1];
4 for i0 ← 1 to ⌊n/2⌋ do
5 for i1 ← 1 to ⌊n/2⌋ do
6 for i2 ← 1 to ⌊n/2⌋ do
7 A[i0] ← A[i0] + A[i0 + i1] − A[i2];
8 s ← s + A[i0];
9 end
10 end
11 end
12 k ← Random(n);
13 if k < 3n/4 then s ← s + func6(A, n − 8);
14 return s
(a) (5 points) What is the asymptotic worst case running time of func6? Justify your solution.
(b) (10 points) What is the asymptotic expected running time of func6? Justify your solution.
7. (15 points) Consider the following recursive function:
1 function func7(A, n)
2 if n ≤ 40 then return A[1];
3 s ← A[1];
4 for i ← 1 to n − 7 do
5 A[i] ← A[i] − A[i + 5];
6 s ← s + A[i];
7 end
8 k1 ← Random(n);
9 k2 ← Random(n);
10 k3 ← Random(n);
11 if k1 < 2n/7 then s ← s + func7(A, n − 4);
12 if k2 < 2n/7 then s ← s + func7(A, n − 9);
13 if k3 < 2n/7 then s ← s + func7(A, n − 15);
14 return s
(a) (5 points) What is the asymptotic worst case running time of func7? Justify your solution.
(b) (10 points) What is the asymptotic expected running time of func7? Justify your solution.
8. (15 points) Consider the following recursive function:
3
1 function func8(A, n)
2 if n ≤ 20 then return A[1];
3 s ← A[1];
4 for i ← 1 to ⌊n/2⌋ do
5 for j ← 1 to ⌊log2
(n)⌋ do
6 A[i] ← A[i] + A[i + j];
7 s ← s + A[i] − A[j];
8 end
9 end
10 k1 ← Random(n);
11 k2 ← Random(n);
12 if k1 < 5n/9 then s ← s + func8(A, n − 8);
13 if k2 < 5n/9 then s ← s + func8(A, n − 13);
14 return s
(a) (5 points) What is the asymptotic worst case running time of func8? Justify your solution.
(b) (10 points) What is the asymptotic expected running time of func8? Justify your solution.
Hint: Pay attention to the sum of the branch probabilities!
E
