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