Hello everyone,

Please see the questions below and try to help me solve them.

1) Given an array of n elements, for each of the following cases suggest an efficient

algorithm for computing in sorted order the k minimal values:

a. k = n / 2

b. k = sqrt{n}

For each case, give a short description of the algorithm and the analysis of the

worst case complexity. Explain your answer

2) Examine the following program:

```
COMPUTE-SUM (A: int array, left: int, right: int) {
i, j, k, n, sum: int;
n = right - left + 1
if (n == 1) then
return;
else {
k = n / 2;
COMPUTE-SUM (A, 1, k)
COMPUTE-SUM (A, k + 1, n)
for i = 1 to n {
j = 1
while (j * j < n) {
j = j + 1
sum = sum + (A[i] * A[j])
{
{
{
print sum
{
```

a. Analyze the algorithm’s complexity, and provide a recurrence relation that

describes it.

b. Based on the above recurrence, find a tight asymptotic bound for the

algorithm’s complexity.

Thanks ahead to the helpers