Search code examples
loopsfor-looptime-complexitypseudocode

Number of multiplications in a pseudo code


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.


Solution

  • 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.