2

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3 

Well I came across this question while learning to figure out complexity of algorithms. How can one go about solving these types of questions its easy to say it has a upper bound of O(n^3) but how to find out exact number of multiplications.

2 Answers 2

3

The following calculations will give the exact number of multiplications in your code.

EDIT: As stated in the comments, the final result can indeed be simplified by two.

4
  • Wow that is some simplification. Thanks a lot mate! Sep 15, 2014 at 0:10
  • 1
    And one more thing could I know the simplification used where (n-j) reduces to j and range changes from j=i->n to j=0->n-i? And also how(n-i)(n-i+1) reduces to i^2+i Sep 15, 2014 at 1:00
  • It's just a variable substitution to get back to the a basic sum of k elements. The only thing is I kept the same name j, which can be a little confusing, but it is the same as if I wrote k = n-j. It might not be crystal clear, but it's quite hard to explain it here in a comment... Is it?
    – BlackDwarf
    Sep 15, 2014 at 1:03
  • You can simplify the final result by two.
    – JulienD
    Oct 5, 2015 at 8:57
0

enter image description here . [sorry , I was unable to use latex here]

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.