Complexity of Function

I'm starting to learn about Complexity Analysis and am finding my text a little hard to understand. Could someone please look at the function below and help work through it explaining how the answer is obtained? I really want to understand the "why" for this topic. Any good resources or suggestions for further reading?

Thanks!

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];
}
Wookie68Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

rstaveleyCommented:
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<--------
WelkinMazeCommented:
Hi there,
What exactly you want to be explained? I mean what is "the answer" you want to be explained?
WelkinMazeCommented:
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.
Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

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

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. :)
Wookie68Author Commented:
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.
WelkinMazeCommented:
See my above answers.
There is a short explanation for the function that you've posted.
Also you can see the links.

btw O(2^n) is one of the worst possible complexities. It's something like reversed of O(log n) which is one of the best.

Here's some of the most common ones ordered by complexity just to see how they go:
O(log n)
O(n)
O(n*(log n))
O(n^2)
O(n^3)
O(2^n)

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Wookie68Author Commented:
Great informatoin in the links you provided.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.