For this pseudocode, how would I express the running time in the Θ notation in terms of n?

s = 0
for i = 0 to n:
for j = 0 to i:
s = (s + i)*j
print s

Question

For this pseudocode, how would I express the running time in the Θ notation in terms of n?

s = 0
  for i = 0 to n:
    for j = 0 to i:
      s = (s + i)*j
print s

anonymous · Answer

for each i in outer for loop , inner for loop will run i times so overall time complexity is excluding this statement $$s = \left(s+i\right)j$$ $$0+1+2+3+4+......+n = \frac{n(n + 1)}{2} \approx O(n^{2})$$ if here s is represented as 32 bit or 64 bit number then cost of multiplication is almost negligible because it will overflow and will just move cyclic from minimum limit to maximum limit. You can see time complexity of general arithmetic operations in more detail in below wiki link https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations But if you want to store all that huge number which you could by using python or something like BigInteger in java then it will be very high. So the big O complexity will change to $$O(n^{2}k)\ where\ k \ is \ maximum\ digit\ length $$ here k could easily exceed n so $$O(n^{3}) $$ would be better interpretation.