Q1.

a. Given an n-element array X, Algorithm B chooses log n elements in X at random and executes O(n)-time calculation for each. What is the worst-case running time of Algorithm B?

b. Given an n-element array X of integers, Algorithm C executes O(n)-time computation for each even number in X, and an O(log n)-time computation for each odd number in X. What are the best-case and worst-case running times of Algorithm C?

c. Sepp and Ueli are arguing about their algorithms. Sepp claims his O(n log n)-time method is always faster than Uelis O(n 2 )-time method. To settle the issue, they perform a set of experiments. To Sepps dismay, they find that if n < 100, the O(n 2 )-time algorithm runs faster, and only when n 100 is the O(n log n)-time one better. Explain how this is possible.

d. Give a big-Oh characterization, in terms of n, of the running time of the method in the following code fragment.

Initialize real number s 0.

for i 0 to n 1 do

for j 0 to n n 1 do

for k 0 to j 1 do

s s + 1

return s