Nested loop analyzing (each loop bounds inner loop)

Question

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(n³). Critical point is that the innermost loop is bounded dynamically.

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

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.

Outline what you’re thinking and we can help you identify problems. Us telling you an answer won’t help you. Only the innermost loop is affected by the outer loops. The middle loop are not affected by the outer. — Jonathan Leffler
– Jonathan Leffler, Commented Mar 7, 2020 at 16:33
That is the point that I confused.Bounding is dynamic , i do not know how to analyze . — nevzatseferoglu
– nevzatseferoglu, Commented Mar 7, 2020 at 16:43
Do you know the quick way of summing up all numbers from 0...1000? I.e. not counting. — Yunnosch
– Yunnosch, Commented Mar 7, 2020 at 16:46
Yes , lets assume that i have a sequence of numbers such {1,2,3,4.......,n} , sum of the all numbers in this sequence must be ( n*(n+1) ) / 2 , isn't it ? — nevzatseferoglu
– nevzatseferoglu, Commented Mar 7, 2020 at 16:49
What do you think is the complexity of the outer loop? What is the complexity of the middle loop? Do what is the complexity of the outer two loops? That gives you part of an answer. The inner loop has a worst case complexity too; what is that? What’s the biggest j can get? So what’s the complexity of the inner loop? And how do you combine that with the previous results? — Jonathan Leffler
– Jonathan Leffler, Commented Mar 7, 2020 at 17:03

chqrlie · Accepted Answer · 2020-03-07 17:33:06Z

3

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 n⁴.

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.

edited Mar 7, 2020 at 17:33

answered Mar 7, 2020 at 17:21

chqrlie

152k12 gold badges145 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

nevzatseferoglu Over a year ago

Did you remove the constant and lower order terms of whole algorithm ?

chqrlie Over a year ago

The algorithm is very simple in your case: one can compute the exact number of iterations, hence the result, with a simple formula. The only low order term is 1 in (n + 1). When you remove that, you get n to the fourth power.

nevzatseferoglu Over a year ago

Could we talk about best , worst and average cases of this algorithm , would it be meaningful ?

chqrlie Over a year ago

@nevzatseferoglu: it does not make much sense to try and distinguish these cases, they are all identical, the number of iterations only depends on n: there is no difference between best, worst and average cases. This distinction is pertinent when analysing algorithms that handle unknown data, for which the behavior depends on their characteristics, such as sorting methods whose performance can vary a lot with the actual distribution of the data set.

chqrlie Over a year ago

@nevzatseferoglu: if an algorithm has conditional statements on variable data, the complexity is more difficult to analyse and best, average and worst case results can be very different. Good examples are en.wikipedia.org/wiki/Quicksort and en.wikipedia.org/wiki/Shellsort.

|

Collectives™ on Stack Overflow

Nested loop analyzing (each loop bounds inner loop)

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related