complexity O n

[sallubhai]

Hi,
Is there anyone who know which complexity these functions are?
I mean O(n), O(n^2), O(n^3), n log(n) or log(n)

1.
---------------------------------------------

void bogosort_array(double a[], int length) {
    do
        shuffle_array(a, length);
    while (! is_array_sorted(a, length));
}

2.
---------------------------------------------

void reverse_string(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n / 2; ++i) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
}

3.
-------------------------------------------------------------

double arrays_are_equal(double a[], double b[], int length) {
    for (int i = 0; i < length; ++i) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

4.
------------------------------------------------------------------------

int find_number_of_matches(int needles[], int haystack[], int length) {
    int nr_matches = 0;
    for (int n = 0; n < length; ++n) {
        for (int h = 0; h < length; ++h) {
            if (needles[n] == haystack[h]) {
                ++nr_matches;
            }
        }
    }
    return nr_matches;
}

5.
-------------------------------------------------------------------------

void sort_array(double a[], int length) {
    for (int sorted = 0; sorted < length - 1; ++sorted) {
        int smallest_in_rest = sorted;
        for (int in_rest = sorted + 1; in_rest < length; ++in_rest) {
            if (a[in_rest] < a[smallest_in_rest]) {
                smallest_in_rest = in_rest;
            }
        }
        double temp = a[sorted];
        a[sorted] = a[smallest_in_rest];
        a[smallest_in_rest] = temp;
    }
}

6.
----------------------------------------------------------------------

void shuffle_array(double a[], int length) {
    for (int randomized = 0; randomized < length; ++randomized) {
        // Select a random position in the rest of the array
        int selected = randomized + rand() % (length - randomized);
        // Swap the current position with the random position
        double oldvalue = a[randomized];
        a[randomized] = a[selected];
        a[selected] = oldvalue;
    }
}

[Adak]

For your sorting functions, look at Wikipedia and search for Sorting algorithms.

In general, if the function just goes through the data, one time, that would be your 0(n), complexity. Since obviously the complexity is directly a product of the number of items being handled, and nothing else.

If it uses nested two nested loops, you have something more - maybe up to (n*n).

If it's nutty like Bogo sort, then it's still worse, of course. ;)

The best general sorters like Quicksort, are n(log n), all others (like your selections sort), are worse, (have higher big O values).

While you're over at Wikipedia, give a read on Big O (oh, not zero), notation. Then try and figure out what's what in your assignment.

When you post code, put tags around it [/CODE ]. Just highlight your code, and click on the code tag icon in the editing window.[CODE ] tags around it [/CODE ]. Just highlight your code, and click on the code tag icon in the editing window.

[sallubhai]

Ok thanks I´ll read there..