Time complexity of an algorithm + suggesting an algorithm for sorting

[ydan87]

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

[rubberman]

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!

[ydan87]

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]).

[rubberman]

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.

[ydan87]

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?

[rubberman]

There are a number of good references online with regard to quicksort and similar algorithms. Here is a link to the wikipedia article: http://en.wikipedia.org/wiki/Quicksort

[Momerath]

I've have the code to several different generic sorts in C# over here with some relative timings.