Be seen. Boost your question’s priority for more expert views and faster solutions

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];

}

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];

}

--------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_iterato

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_itera

nth_element(b,b+k,b+n);

cout << "b: ";copy(b,b+n,ostream_itera

partial_sort(c,c+k,c+n);

cout << "c: ";copy(c,c+n,ostream_itera

}

--------8<--------

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

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.

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

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.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

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)