Search code examples
cfor-loopcomplexity-theory

Nested loop analyzing (each loop bounds inner loop)

  • In my data structure lecture, I got homework about algorithms and time complexity. I could not actually find what I need to do for this.

Question : What is the time-complexity of this algorithm ?

  • My solution was the analyzing loop by loop, removing constant and lower order terms of each of loop itself. For this reason , there are three loops within each other. Complexity should be O(n3). Critical point is that the innermost loop is bounded dynamically.

What is the mistake on this table ( if there is ) :

enter image description here

int c = 0;
for (int i = 0; i < n * n; ++i)
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < j * 2; ++k)
            c = c + 1;
return c;

All answers are welcomed.

Solution

  • In order to compute the time complexity, you can try and evaluate the number of iterations of the innermost loop.

    • the loop on k evaluates a simple expression 2 * j times.
    • the loop on j runs n times. Hence the inner loop runs 2 * n * (n + 1) / 2, which simplifies to n * (n + 1).
    • the outer loop runs n * n times. Hence the inner loops runs exactly n * n * n * (n + 1) times.

    Simplifying for the dominant term, the resulting time complexity is n4.

    Yet a very shrewd compiler would reduce this complexity to constant time O(1) and generate code for:

    return n * n * n * (n + 1);

    Trying this on Godbolt's compiler explorer shows that none of the common compilers achieve this as of now, albeit clang goes to great lengths trying to optimize the code with unfathomable SIMD code.