algorithm - Big O Question - Algorithmic Analysis II -

i doing question asks find complexity of nested loop simplified using big o notation.

the question is:

for <- 1 n     j <- 1 n         k <- 1 (i+j)             unit cost operation 

i have prove above using sum of series notation. kind of grasping concept , have given crack. want know whether doing correctly or not.

here answer:

**assume sum(x=i, y) capital sigma notation x lower bound , y upper bound.

=> sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1
=> sum(i=1, n) sum(j=1, n) (i+j)
=> sum(i = 1, n) n*i => n * sum (i = 1, n) i

subbing in rule sum of arithmetic series gives: => n*n/2(n+1) => (n^3 + n^2) / 2

using big oh rule -> max(f(x), g(x)): => max(n^3/2, n^2/2) => o(n^3)

i know answer correct not sure if calculations prior are....

with small correction:

  sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1 = sum(i=1, n) sum(j=1, n) (i+j) = [ sum(i=1, n) sum(j=1, n) ] + [ sum(i=1, n) sum(j=1, n) j ] =   sum(i = 1, n) n*i           +   sum(i=1, n) n*(n+1)/2  =   n * sum (i = 1, n)        +   n * n * (n+1) / 2 =   n * n * (n+1) / 2           +   n * n * (n+1) / 2 =   n * n * (n+1) =   n^3 + n^2 =   o( max(n^3, n^2) )           <--- correctly =   o(n^3) 

actually, it's Θ(n^3)

---

you use i+j <= 2*n:

   sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1 =  sum(i=1, n) sum(j=1, n) (i+j) <= sum(i=1, n) sum(j=1, n) 2*n =  2*n * sum(i=1, n) sum(j=1, n) 1 =  2 * n^3 =  o(n^3)