Complexity of Function

The name suggests that you've got something like an nth_element algorithm, but maybe it is a partial_sort. I guess a complexity analysis would tell you that a nth_element algorithm can afford to be less complex than a partial sort. I shouldn't really be commenting. I didn't do CS, so what do I know? 8-)

--------8<--------
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

int selectkth (int a[], int k, int n){
     int i, j, mini, tmp;
     for (i=0; i<k; i++){
          mini = i;
          for (j = i+1; j < n; j++)
               if (a[j]<a[mini])
                    mini=j;
          tmp = a[i];
          a[i] = a[mini];
          a[mini] = tmp;
     }
     return a[k-1];
}

int main()
{
      int a[20];
      const int n = sizeof(a)/sizeof(*a);
      int k = n/2;
      srand(time(0));
      generate(a,a+n,rand);
      copy(a,a+n,ostream_iterator<int>(cout,","));cout << endl;

      int b[n],c[n];
      copy(a,a+n,b);
      copy(a,a+n,c);

      cout << k << "th element from selectkth is: " << selectkth(a,k,n) << '\n';
      cout << "a: ";copy(a,a+n,ostream_iterator<int>(cout,","));cout << endl;

      nth_element(b,b+k,b+n);
      cout << "b: ";copy(b,b+n,ostream_iterator<int>(cout,","));cout << endl;

      partial_sort(c,c+k,c+n);
      cout << "c: ";copy(c,c+n,ostream_iterator<int>(cout,","));cout << endl;
}
--------8<--------

Hi there,
What exactly you want to be explained? I mean what is "the answer" you want to be explained?

As I see the function actualy finds the k-th element of an array with n elements using sorting of the first k elements. This way the k-th element in growth of the array is the element at k-1 position.
The complexity of the function has to be O(k*n). And it is such cause you have 2 loops. Each n iterations of the secon ones are executed for each iteration of the first one. The first one has k iterations and the secon one has n iterations. So the complexity is k*n.

"secon ones" in previous post has to be "second one".
sorry :(

Here you can find in a few words something about complexity analysis:
http://www.daniweb.com/techtalkforums/thread13488.html

Here you can find comparison between different sorting algorithms, they are among the ones that are used most often for example in this area:
http://linux.wku.edu/~lamonml/algor/sort/sort.html

Here you can download a book in pdf format about Algorithms and Complexity:
http://www.cis.upenn.edu/~wilf/AlgComp3.html

And you can find many more materials if needed using google. :)

This is actually an exercise froma book I borrowed from a friend to learn from . The question actually reads: Find the complexity of the function used to find the kth smallest integer in an unordered array of integers. It then lists the funtion I originally put in. This is in a section called Big-O notation.

The more I read, it is focusing on creating algorithms smartly...ones that won't take forever to run. A lot of examples show the answers something like f(n)=5n+1  or O(2^n). I was just trying to understand how to calculate the complexity of the function based on the loops and such in it.

Great informatoin in the links you provided.