Nested loop with dependent bounds trip count

Posted by aaa on Stack Overflow See other posts from Stack Overflow or by aaa
Published on 2010-05-14T06:07:10Z Indexed on 2010/05/14 6:14 UTC
Read the original article Hit count: 211

Filed under:
|
|
|

hello.

just out of curiosity I tried to do the following, which turned out to be not so obvious to me; Suppose I have nested loops with runtime bounds, for example:

 t = 0 //  trip count
 for l in 0:N
   for k in 0:N
     for j in max(l,k):N
        for i in k:j+1
           t += 1

 t is loop trip count

is there a general algorithm/way (better than N^4 obviously) to calculate loop trip count? I am working on the assumption that the iteration bounds depend only on constant or previous loop variables.

© Stack Overflow or respective owner

Related posts about theory

Related posts about algorithm