Search code examples
analysisnotationbig-o

Express Running time in Big Theta Notation ?

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
Solution

  • The assignment s = (s+i)*j has constant time-complexity Θ(1). For each i the inner loop gets executed exactly i times, whereas i is iterated from 0 to n. So the body of your loop (eg. the assignment) is executed 1+2+3+...+(n+1) = (n+1)(n+2)/2 = Θ(n^2).

    As the body of the loop is Θ(1) you get Θ(n^2) for the whole program noting that the first and last lines are just Θ(1) so you can ignore them.