Time Complexity

Question

I think answer should be $O(n^{3})$

but given options are

$a.O(n^{4}) b.O(n^{5}) c.O(n^{6}) d.O(n^{7})$

What is the running time of the following code:

Consider following code fragment
(1) for i in $1 . . \mathrm{N}$ loop
(2) for j in $1 . . \mathrm{i}$ loop
(3) for k in 1 ...j loop
(4) sum: $=$ sum +1
(5) end loop:
(6) end loop;
(7) end loop:
(8) for p in $1 . . \mathrm{N}^{*} \mathrm{~N}$ loop
(9) for $q$ in I..p loop
(10) sum:=sum-1:
(11) end loop:
(12) end loop:

Comments

it will be O(n⁴)

upper combined loop(i,j,k) is giving O(n³)

lower combined loop(p,q) is giving O(n⁴) since it is 1+2+3+4.......n² = O(n⁴)

now total time= O(n³) + O(n⁴) = O(n⁴)

---

can you explain second last line how did you solve this series?

---

it is sum of first n² numbers = $\frac{n^{2}(n^{2} + 1)}{2}$ = O(n⁴)

---

upper combined loop(i,j,k) --->how O(n3)?? coz i=will run n time j=n time k=n(n+1)/2 =n2 O(n4)??? where i m doing mistake plz guide me.

@joshi_nitish

Answer 1

For loop(Line no 1-7):

if n =1, i = 1, j = 1 time, k = 1 time
if n = 2, i = 2, j = 2 times, k = (1+2) times
if n = 3, i = 3, j = 3 times, k = (1+2+3) times
if n = n, i =n, j = n times, k = (1+2+3+-----+n) times

1+(1+2)+(1+2+3)+-----+(1+2+3+----+n)
so, time complexity = O(n^3)  

For loop(Line no. 8-12):
if n = 1, p = 1^2, q = 1^2
if n = 2, p = 2^2, q = 1+2+3+2^2
if n = 3, p = 3^2, q = 1+2+----+3^2
if n = n, p = n^2, q = 1+2+3+-----+n^2

So, time complexity  = O(n^4)

So, Time complexity of the program is = O(n^3+n^4) = O(n^4)

Comments

For loop(Line no 1-7):
T.C will be O(n^3)

---

Is it correct now?