3

Say I have k for loops nested in the following fashion:

for a = 1 to n:
    for b = 1 to n-a:
        for c = 1 to n-a-b:
            for d = 1 to n-a-b-c:
                O(1)

for any arbitrary k, but all k of these loops "share" the limit of n iterations with each other, is the big-O complexity still O(n^k)? Or is it some order below that?

Edit: What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? is indeed asking something similar but it wasn't asking (nor does the answer address) if additional levels of nesting will change anything.

Dmitry's answer explains it very well for me.

Community
  • 1
  • 1
Andy Law
  • 33
  • 3
  • Possible duplicate of [What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?](http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop) – dee-see Oct 22 '16 at 19:35

1 Answers1

2

OK, let's sum them all up: using induction you can find out that numbers of loops (for large n > k) are:

  1. n 
  2. n * (n - 1) / 2 
  3. n * (n - 1) * (n - 2) / 6
  ...
  k. n * (n - 1) * ... * (n - k + 1) / k!
  ...

As you can see the complexity is O(n**k) as you've conjured for any k providing that n is large enough (n > k).

Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215