Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why is the complexity class expression this?

  1. Jan 29, 2016 #1
    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. jcsd
  3. Jan 29, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook