ADA

Question

For p in1..N*N loop

For q in 1..p loop

Sum=Sum-1

What is the running time for sum statement?I think it will be 1+2+3+4..N^2.But how to slove this?

Answer 1

your code looks like

for (p=1 to n*n)
    for(q=1 to p)
            sum=sum-1

time complexity of the above snippet will be equal to number of times  "sum=sum-1" runs.

p	q
1	1
2	2
3	3
......	.....
n*n	n*n

$T\left ( n \right )=1+2+3+...n^{2}=\left ( n^{2}*\left ( n^{2}+1 \right ) \right )/2$=O$\left ( n^{4} \right )$

Comments

T(n)=1+2+3+...n2=(n2∗(n2+1))/2T(n)=1+2+3+...n2=(n2∗(n2+1))/2=O(n^4) not n^2

---

updated !thankx