Total number of iterations in $d$ nested for loops

726 Views Asked by At

Assume that there are $d$ number of for loops in a computer program. Let it be for example Matlab. A pseudo code will look like this:

for i=1:N
   for j=i:N
      for k=j:N
         ..
         ..
      do something (costs one operation)
      end
    end
end

a. How many operations are performed altogether in terms of $N$ and $d$. Is there any formula for this?

b. Is there any way to write a computer program for example in Matlab, which will automatically create $d$ such for loops whenever the number $d$ is given?

Added: A combinatorics correspondance of the problem is the $d$-tuple combinations of numbers ranging from $1$ to $N$ without regarding the ordering. For example triple combinations of numbers from $1$ to $3$:

$(1,1,1),(1,1,2),(1,1,3)...(3,3,3)$ here we do not have the terms $(1,2,1)$ and $(2,1,1)$ because they are the same with $(1,1,2)$. The same goes to for example $(1,3,1)$ and $(3,1,1)$ etc.

1

There are 1 best solutions below

6
On BEST ANSWER

If you were iterating through all choices of $d$ distinct values from a set of $N$, the total number of such choice is given by the binomial coefficient $$\binom Nd= \frac{N!}{(N-d)!\cdot d!}$$

The total number of choices here is all choices of nondecreasing values; this can be transformed into the above case by adding $(0,1,2,...,d{-}1)$ to the values, meaning the result is $$\binom {N+d-1}d= \frac{(N+d-1)!}{(N-1)!\cdot d!}$$

You can iterate across these options without nested for loops by retaining an array of values and incrementing suitably, but that's not really a mathematics question.