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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Oct 18, 2016 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
    Commented Oct 18, 2016 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
    Commented Oct 18, 2016 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
    Commented Oct 18, 2016 at 22:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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