Why is the complexity class expression this?

Tags:
1. Jan 29, 2016

Xari

I'm trying to understand complexity class algorithms off of my professor's lecture notes, but I still can't get a hang of it.

void sort(int a[], int N) { //N is the length of the array
for (int base=0; base<N; ++base)
for (int check=base+1; check<N; ++check)
if (a[base] > a[check])
std::swap(a[base], a[check]);​
}

On his notes he says the expression for this is 8N^2+12N+6.

From what I understand fully the complexity class for this is N^2 because it is the fastest growing out of the rest. We ignore constants because they're irrelevant when going to infinity.

However, I want to know how he got the coefficients.

2. Jan 29, 2016

Samy_A

I don't think one can answer this question with the information given. It depends on how the compiler translates the C++ code into machine language.
Probably the precise 8N²+12N+6 formula was empirically derived with a given compiler for a worst case scenario.
Or maybe these values are just arbitrary. The number of instructions executed in a worst case scenario will be given by a second-degree polynomial (N for the first loop, N/2 on average for the inner loop) in N.

Last edited: Jan 29, 2016