4 ms·

Before I begin just let me say I am not a mathematician. I program so that I don't have to do complex math. I know in reality the frequency of iterations vari

Before I begin just let me say I am not a mathematician. I program so that I don't have to do complex math. I know in reality the frequency of iterations varies considerably but for simplicity of discussion let's remove variability. Say we have a loop with 1000 iterations. That is at minimum 1000 statements in the loop body plus expression overhead from the loop itself. If this loop is nested once with a same sized loop there are now 1,000,000 iterations plus some expression overhead per iteration. If it is nested twice deep there are now 1 billion iterations. That example is exponential of 1000. Given that there is overhead associated with operation of a loop it is actually greater than exponential. It may not be quite so dramatic as a logarithmic growth curve though. I completely concede that in reality loops vary in iteration count and so nested loops aren't likely perfectly exponential unless their iteration counts are identical. The increase of iterations from nesting loops does increase more dramatically than a simple multiplicative operation as the depth of loop nesting increases, such that the growth of total iterations is a curve on a graph. A polynomial growth operation when graphed should present a straight diagonal line without the presence of a third variable.

mlevental 9y ago
>that example is exponential of 1000. no it's not. you simply have the definitions mixed up. exponential slow down or speed up means a^x where x=1000. you are describing polynomial growth, i.e. x^a (where x=1000 and a=3)
- yorwba 9y ago
  It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad.
  - whatyoucantsay 9y ago
    > "It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad." Adding more nested loops is bad, but it's not exponential. It's polynomial. As you nest more and more loops, the big O complexity goes from N to N^2 (quadratic) to N^3 (cubic) to N^4, etc... N^(any number) is polynomial. Exponential would be 2^N or 3^N or any number raised to the N. See: https://en.wikipedia.org/wiki/Exponential_growth https://en.wikipedia.org/wiki/Exponential_growth
    - dbaupp 9y ago
      In this case, the number of iterations (1000) of each loop is being held fixed, and the depth of nesting is varying, i.e. the body of the inner loop executes O(1000^depth) times.
      - colanderman 9y ago
        Nitpick: "O(…) times" is nonsensical. O-notation applies only to behavior in the limit. Notably, O(some constant) is exactly equivalent to O(1).
        yorwba 9y ago
        In this case depth is not constant, so 1000^depth isn't either. And usually when you encounter O(some constant), it's meant as "of the order of magnitude of", i.e. somewhere between some constant/10 and some constant * 10. That isn't the definition used here, but seems to be the cause of most complaints about asymptotic analysis being misapplied when no asymptotic analysis was being done in the first place.
        colanderman 9y ago
        See my answer to the GP. `depth` – the lexical nesting depth of "for" loops in the program text – is constant with respect to any given algorithm.
        dbaupp 9y ago
        What exactly are you nitpicking? 1000^depth is not a constant: the function here is "f(depth) = number of times the inner loop body executes". f(depth) = O(1000^depth). And, "times" here is serving the same role as "comparisons" in "Mergesort takes O(n log n) comparisons": it's referring to the thing that f is actually counting.
        colanderman 9y ago
        Given O(f(x)), x is almost always understood to be measurement of the work input to the algorithm. Loop nesting depth is not a measurement of work input, it's a property of the code – "1000^depth" is constant for any given algorithm. Yes, O(…) is just a mathematical construct, so you can apply it the way you have to mean "the amount of work done for a given input size increases exponentially with respect to the number of nested loops iterating over the input"… but that's not how most people interpret it in the context of a computer algorithm. (The exception would be if the nesting depth were dynamically determined by an input parameter, but I don't think that's what anyone here is talking about.) Anyway I'm not trying to argue, I agree with your point, but I think everyone here is talking past each other trying to say the same thing, ultimately due to imprecision in semantics.
Ar-Curunir 9y ago
You won't have random extra nested loops appear out of nowhere in your code
tachyoff 9y ago
I wouldn’t call time complexity particularly complex math. Imagine a loop. It does something n times. Within that loop, you do something n times. For each outer looo through n,you do an inner loop through n. Trivially, this is n*n, or n^2, also known as quadratic time. If you nest another loop, it becomes n^3, or cubic time. Anyway, there might be some confusion of terms, perhaps. Exponential time in the algorithmic complexity sense is any algorithm that takes 2^n operations to complete. If you’re talking about the number of iterations after you loop through n things n times, then that increase itself would not be exponential. But that delta in iterations is unrelated to exponential and polynomial time complexity.
- austincheney 9y ago
  I am sooo not a math person. Let's not forget there is overhead to loops. At a minimum let's assume there is a single statement in the loop body, an increment statement and a terminal condition. In a single loop of 1000 iterations there are 3000 things to evaluate. The math becomes: (n * 3)^x If a simple loop is nested twice (3 depths) there would be 1 billion iterations but about 27 billion evaluations. Would it be correct to say that is just slightly faster polynomial growth?

mlevental 9y ago

>that example is exponential of 1000. no it's not. you simply have the definitions mixed up. exponential slow down or speed up means a^x where x=1000. you are describing polynomial growth, i.e. x^a (where x=1000 and a=3)

yorwba 9y ago
It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad.
- whatyoucantsay 9y ago
  > "It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad." Adding more nested loops is bad, but it's not exponential. It's polynomial. As you nest more and more loops, the big O complexity goes from N to N^2 (quadratic) to N^3 (cubic) to N^4, etc... N^(any number) is polynomial. Exponential would be 2^N or 3^N or any number raised to the N. See: https://en.wikipedia.org/wiki/Exponential_growth https://en.wikipedia.org/wiki/Exponential_growth
  - dbaupp 9y ago
    In this case, the number of iterations (1000) of each loop is being held fixed, and the depth of nesting is varying, i.e. the body of the inner loop executes O(1000^depth) times.
    - colanderman 9y ago
      Nitpick: "O(…) times" is nonsensical. O-notation applies only to behavior in the limit. Notably, O(some constant) is exactly equivalent to O(1).
      - yorwba 9y ago
        In this case depth is not constant, so 1000^depth isn't either. And usually when you encounter O(some constant), it's meant as "of the order of magnitude of", i.e. somewhere between some constant/10 and some constant * 10. That isn't the definition used here, but seems to be the cause of most complaints about asymptotic analysis being misapplied when no asymptotic analysis was being done in the first place.
        colanderman 9y ago
        See my answer to the GP. `depth` – the lexical nesting depth of "for" loops in the program text – is constant with respect to any given algorithm.
      - dbaupp 9y ago
        What exactly are you nitpicking? 1000^depth is not a constant: the function here is "f(depth) = number of times the inner loop body executes". f(depth) = O(1000^depth). And, "times" here is serving the same role as "comparisons" in "Mergesort takes O(n log n) comparisons": it's referring to the thing that f is actually counting.
        colanderman 9y ago
        Given O(f(x)), x is almost always understood to be measurement of the work input to the algorithm. Loop nesting depth is not a measurement of work input, it's a property of the code – "1000^depth" is constant for any given algorithm. Yes, O(…) is just a mathematical construct, so you can apply it the way you have to mean "the amount of work done for a given input size increases exponentially with respect to the number of nested loops iterating over the input"… but that's not how most people interpret it in the context of a computer algorithm. (The exception would be if the nesting depth were dynamically determined by an input parameter, but I don't think that's what anyone here is talking about.) Anyway I'm not trying to argue, I agree with your point, but I think everyone here is talking past each other trying to say the same thing, ultimately due to imprecision in semantics.

Ar-Curunir 9y ago

You won't have random extra nested loops appear out of nowhere in your code

tachyoff 9y ago

I wouldn’t call time complexity particularly complex math. Imagine a loop. It does something n times. Within that loop, you do something n times. For each outer looo through n,you do an inner loop through n. Trivially, this is n*n, or n^2, also known as quadratic time. If you nest another loop, it becomes n^3, or cubic time. Anyway, there might be some confusion of terms, perhaps. Exponential time in the algorithmic complexity sense is any algorithm that takes 2^n operations to complete. If you’re talking about the number of iterations after you loop through n things n times, then that increase itself would not be exponential. But that delta in iterations is unrelated to exponential and polynomial time complexity.

austincheney 9y ago
I am sooo not a math person. Let's not forget there is overhead to loops. At a minimum let's assume there is a single statement in the loop body, an increment statement and a terminal condition. In a single loop of 1000 iterations there are 3000 things to evaluate. The math becomes: (n * 3)^x If a simple loop is nested twice (3 depths) there would be 1 billion iterations but about 27 billion evaluations. Would it be correct to say that is just slightly faster polynomial growth?