Explain why this unsimplified complexity expression is this?

Question

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

I don't understand how he got the + 6. What exactly is run only a total of 6 times when this function is called once? I see that int base = 0 is created only once because it belongs on the outer for-loop.

Edit: So I found how the + 6 is simply the bare minimum this function needs to run. In the case that the for-loops are executed only once... so the total lines? Well we make a copy of a[] and int N, then we have our for-loops and if statement. Altogether everything adds to 6.

What about the 12N?

isn't this code just bubblesort? i don't know what thish should have to do with the rest (why do you ned int N? you know this Information already by something like a.Length) — M. Schena, Jan 29 '16 at 06:34
The only thing correct here is the *n²* complexity. The constants are all made up. What does 6 mean here? 6 what? on what platform? Since the constants are made up, you can make up that the inner loop runs at 12 per iteration or anything. It's sort of bullsh*t, I must say. — Ami Tavory, Jan 29 '16 at 06:36
You can get these constants only if you assume some execution times for the basic elements in this algorithm. We don't know how your professor defined these. However as @AmiTavory already pointed out, this is irrelevant in practice. — Henry, Jan 29 '16 at 06:54

score 3 · Accepted Answer · edited May 23 '17 at 12:33

As Ami Tavory suggest this looks like bullshit. After more close look it still is very weird as the expression is mixing cycles of very different operations as it would be atomic ... If I ignore the relevancy I see it like this:

void sort(int a[], int N) {                    // ?T
   for (int base=0; base<N; ++base)            // 1 +(3+2)N
      for (int check=base+1; check<N; ++check) // 2N+(3+2)M
         if (a[base] > a[check])               // (2+1+2)M
            std::swap(a[base], a[check]);      // (2+2+2)M
}

Where I did wild assumptions about how many cycles are for memory/register/direct access or ALU operations. The M = ~ (N^2)/2 (sorry too lazy to get the actual count from the series sum) is the number of inner loop iterations. So when I sum all together I got:

16*(N^2)/2+7N+1+?
8*N^2 + 7N + 1+?

Which is pretty close to your expression. As I used inaccurate M and do not know the architecture behind this the result might change a bit possibly in favor of your expression. So the function init and return is accounted for ~5 cycles. If I got even wilder then that:

int a[]; // 2 // heap -> reg
int N;   // 2 // heap -> reg
 {}      // 1 // stack return (I would guess it should be also 2)

so I got:

8*N^2 + 7N + 6

against yours:

8*N^2 + 12N + 6

To make this accurate you should:

compute the M exactly
get the timings of operations for the architecture this is for
break the code to atomic operations

distinguishing direct/memory(heap/stack)/register access (may be even read/write), ALU operations and more... For example the swap(a,b) { c=a; a=b; b=c; } if it is not done by Xoring ... And now you can count the cycles like I tried ...

For example look here Machine cycle timings for Z80 where is a link to my Zilog Z80A complete instruction set with machine cycle timing. So you can see how different each type of instruction really is. You should have something similar for the platform/architecture you are learning this stuff on.

Thank you very much for responding. The scenario I gave you was in his lecture notes and I couldn't understand it no matter how many times I went over it. Knowing that it's pretty much bullshit is comforting. I know at least that I understand complexity classes now. — Jacob Macallan, Jan 30 '16 at 21:23

Explain why this unsimplified complexity expression is this?

1 Answers1