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

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

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;

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.

0

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

0

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.

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