CODEWITHSUNDEEP
analysisnotationbig-o
user2990394
user2990394

Reputation: 55

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

Upvotes: 0

Views: 327

Answers (1)

gen
gen

Reputation: 10040

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.

Upvotes: 1

Related Questions