0
$\begingroup$

I am trying to count the exact/total number of iterations these nested for-loops are executed:

procedure P (integer n);
 for (i: 1 to n)
  for (j: 1 to 10)
   for (k: n to n+5)
    x := x + 1;

I know that the first for loop runs (n-1) times, the second loop runs 10-1 (9) times, thus making the time complexity so far 9(n-1). I know that the the third loop will run n+5-n (5) times, but I am not completely sure because of the n involved. I believe with this calculation added, the total runtime will be 5(9(n-1)) which will translate to O(n). In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates. Thanks in advance.

$\endgroup$
  • $\begingroup$ your calculation is to the point. Irrespective of the value which n takes the third loop will run 6 times , don't be confused about the n . $\endgroup$ – Shubham Singh rawat Oct 18 '16 at 5:32
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Oct 18 '16 at 9:06
  • $\begingroup$ Using pattern matching won't get you far; use a structured approach instead. Note that you don't really analyse "time" -- what exactly are you counting? $\endgroup$ – Raphael Oct 18 '16 at 9:33
  • $\begingroup$ @DavidRicherby I think the question is fine (if not great) because (after reading the reference question) it can be read to ask "is this simplifying view on the general technique valid?" $\endgroup$ – Raphael Oct 18 '16 at 22:45
0
$\begingroup$

In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates.

Basically, yes. But you don't really multiply: As explained here at length, you have nested sums. In your case,

$\qquad\displaystyle \sum_{i=1}^n \sum_{j=1}^{10} \sum_{k=n}^{n+5} 1$

(if we count the number of assignment operations) is easy to evaluate because the loops do not depend on each other. It looks like multiplication here, but if you get things like

  for i = 1 to n
      for j = 1 to i
          foo

that does not work anymore.

Note that worst-case considerations and asymptotics do not enter the picture here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.