0

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

3
Contributors
6
Replies
9
Views
6 Years
Discussion Span
Last Post by Momerath
0

Sorry, but we are not going to do your homework for you! Make an effort first, and then we may critique it and give you some pointers, but don't expect a 4 course meal for free!

0

Sorry, but we are not going to do your homework for you! Make an effort first, and then we may critique it and give you some pointers, but don't expect a 4 course meal for free!

Actually, I've done a few attemps to solve this, I just wanted to check them...
For the first question, because of the fact that the input might be really big, it's better to sort the entire array with an algorithm of O(nlogn) and then we have the k minimal elements sorted as well.

For the second one I've tried to do a recurrence relation and calculating the time comlexity...I think I've ended up with O(n[TEX]sqrt{n}[/TEX]).

0

I have found that an insertion sort - a modified qsort, that inserts items in the appropriate place in an array, is extremely effective and efficient. I wrote a class some time ago to do that, and it could handle very large numbers of entries very efficiently. I also optimized for head/tail insertions so that either sorted or reverse-sorted inputs would go in quickly. If you already have your data in an array or vector, then a quicksort would be best using qsort(), or a b-tree.

0

yes a quicksort was just my thought. Because the data is already in the array so as you said quicksort will be better here.

What about the time complexity of that program above?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.