suppose have following loop:
for (int = 0; < n; i++) (int j = i+1; j < n; j++) (int k = j+1; k < n; k++) (int l = 0; l < n; l++) i understand first loop loop n times.
i think second 1 going run (1/2) * (n^2 + n - 2) times because we'd need calculate sum 2 n, not 1 n.
however, have no idea third , fourth ones.
there (at least) 2 ways understand time complexity: first involves noting 3 nested for-loops generate precisely 3-subsets of n-set, , second 1 "direct" approach.
combinatorial argument
the first 3 for-loops choose precisely 3-subsets of n-set, each 3-subset once (think it). there (n choose 3) = o(n^3) such subsets (see here). innermost loop o(n) work each of o(n^3) iterations of other 3 loops, total time o(n^4).
the 3 loops (without innermost one) make n choose 3 = n!/(3!(n-3)!) iterations. n*(n-1)*(n-2) / 6 iterations.
direct argument
the innermost loop execute n times regardless of other loops, time complexity o(n * f(n)), f(n) time complexity of other 3 loops if remove innermost one.
the 2 innermost loops (the j- , k-indexed ones) take o(i^2) time. easy see---it same having double-loop j=0 i-1 , k=j i-1, time o(1) + o(2) + ... + o(i) = o(i^2).
because outtermost loop goes i=0 n-1, total complexity n * (o(1^2) + o(2^2) + ... + o(n^2)), o(n * n^3): outtermost loop (i-indexed) executes double for-loop (j- , k-indexed) i=0 i=n-1.
we have o(n^4) total running time.
to exact number of iterations, have compute sum of terms i*(i-1)/2 = (i^2-i)/2 suitable i's. let's sums , divide 2 in end.
you can break 2 sums,
(1^2 + 2^2 + ...n-1) - (1 + 2 + ... + n-1) = = n(n-1)(2n-1)/6 - n*(n-1)/2 = = n*(n-1)(n-2)/3 now divide 2 , result n*(n-1)*(n-2)/6. same above. (see how compute sum of first n squares.)
Comments
Post a Comment