Calculate the worst-case running time of the algorithm using Big-Oh notation. Indicate how you arrived at the answer. Then give the name of the Big-Oh complexity.

Question

Pestiferous(n)

r=0

for i = 1 to n do

for i = 1 to i do

for k = j to i + j do

for l = 1 to i + j - k do

r = r + 1

return(r)

Answer 1

The most outer loop runs n times -> So far O(n)

For each iteration of the outer loop, the second loop runs n times at the worst case -> So far O(n²)

For each iteration of the second loop, the third loops runs 2n times at the worst case -> So far O(n² * 2n) = O(n³)

For each iteration of the third loop, the fourth loop runs 2n times at the worst case -> Finally we get O(n³ * 2n) = O(n⁴)

Through out these steps, any coefficients that appeared were simply removed in the big-o notation as is per the rule:

If f(n) is O(g(n)), then kf(n) is O(g(n)), for any constant k > 0.

Which really means that in the case of large input sizes n approaching infinity, the coefficients are do not matter.

Another way you could've solved the problem is by realizing that the loops all run a number of times that can be described as a linear function of n. Using the product rule and multiplying 4 linear functions of n, the final polynomial's largest term will be n⁴, hence the algorithm runs in O(n⁴).