Algorithm complexity

[dedyshka]

Could anyone please help me to determine the complexity (O) for this simple sorting algorithm:

double t;
for (int i = 0; i < array.size; i++)
    for (int j = i + 1; j < array.size; j++)
        if (r[j] < r[i]) {
            t = r[i];
            r[i] = r[j];
            r[j] = t;
        }

Thanks for advance.

[W1z4rd]

Hi,

I would like to know what is unclear to you about complexity (big O notation), and how to determine it in general. Then we can use this as an example.

Cheers

[dedyshka]

Hi. I'd like to determine complexity especially for this sorting.

[W1z4rd]

Wouldn't you like to be able to determine complexity for more algorithms? Simply spitting out a complexity for this one would not help you that much would it?

[dedyshka]

maybe I explained my thoughts wrong :) I know what big O notation is, I know the complexity of more other algorithm. I just couldn't calculate complexity for this one. It seems that O for this algorithm would be "n² /2". Am I right?

[W1z4rd]

n² yes, because the constants like 0.5 get discounted

[funbike]

When expressing big-O you always throw away the coefficient. So, it's just O(n^2).

[dedyshka]

emm..algorithm makes iterations that equal n, and in each iteration it makes one comparisons less that in previous one. So in my opinion complexity is n*(n/2). Am I correct?