CSE 2331 Homework 5
Please do not write on the question sheet. You must show all work to receive any credit.
Give the best case, worst case, and average case asymptotic running time of each the
following functions in Θ notation. Justify your answer. In the code below, random(n) returns
i ∈ [n] with probability 1/n, in Θ(1)-time. Further, CoinFlip simply returns random(2)− 1.
1.
1 def func1(xs):
2 s← 0;
3 n← len(xs);
4 k ← random(n);
5 m←
√
n;
6 if k = 1 then
7 m← n/2;
8 end
9 for j ← 0 to m do
10 s← s ∗ xs[j];
11 end
12 return s;
13 end
2.
1 def func2(xs):
2 s← 0;
3 n← len(xs);
4 k ← random(n);
5 m← log2 n;
6 if k < pow(n, 0.25) then
7 m← n/2;
8 end
9 for i← 0 to n/2 do
10 for j ← 0 to m do
11 s← s ∗ xs[j] + xs[i];
12 end
13 end
14 return s;
15 end
3.
1 def func3():
2 s← 0;
3 while CoinFlip() = 0 do
4 s = s + 1;
5 end
6 return s;
7 end
4.
1 def func4(xs):
2 i← len(xs);
3 while i > 0 do
4 if random(10000) == 1 then
5 return -1 ;
6 end
7 i = i− 1;
8 end
9 return i;
10 end
5.
1 def func5(xs):
2 s← 0;
3 n← len(xs);
4 if n ≤ 10 then
5 return xs[1] ;
6 end
7 k = random(100);
8 if random(nk) == 1 then
9 for j ← 0 to nk do
10 s← s ∗ xs[j] + xs[j];
11 end
12 end
13 return s;
14 end
6.
1 def func6(xs):
2 s← 0;
3 n = len(xs);
4 while random(n) 6= random(n) do
5 s = s + xs[random(n)− 1];
6 end
7 return s;
8 end
7.
1 def func7(xs):
2 s← 0;
3 n = len(xs);
4 if n ≤ 5 then
5 return xs[1] ;
6 end
7 while random(n) 6= random(n) do
8 s = s + xs[random(n)− 1];
9 end
10 if random(n) ≤ 2 ∗ n/3 then
11 return func7(xs[:n//2]);
12 end
13 return s;
14 end