Time Complexity Problem -Urgent

[panzerss]

What would be the time complexity (worst case) of following:
I have three loopes.
n=number of elements

for(i=0;i

[loveleen]

hi,
the soln is as follows...
Value of i changes from 0 to n-2
Value of j changes as follows..1 to n-1
2 to n-1
.....
n-2 to n-1

Value of k changes as followsFor j=1 to n-12 to n
3 to n
4 to n
.....
n to n

for j=2 to n-13 to n
4 to n
....
n to n

......
for j= n-2 to n-1n-1 to n
n to n


Thus total number of executions is summation of number of times value of k changes which is

=(n-2)(n to n)+(n-2)(n-1 to n)+(n-3)(n-2 to n)....1(2 to n)
=(n-2)(n to n)+(n-2)(n-1 to n)+(n-3)(n-2 to n)....1(2 to n)+0(1 to n)
=(n-2)(1) + [(n-2)2+(n-3)3+......+(1)(n-1)+(0)(n)]
=(n-2)(1) + [ summation of (n-i)i ] where i =2 to n
=(n-2)(1) + [ summation of (n-i)i ] - n +1 where i= 1 to n

the rest can be solved easily using the formulas
1+2+3....n= n(n+1)/2
1^2+2^2....n^2=(n)(n+1)(2n+1)/6

[navaraj]

hi,i have a doubt in this.

For j=1 to n-12 to n
3 to n
4 to n
.....
n to n
it should be like this right ?
For j=1 to n-12 to n
3 to n
4 to n
.....
n-1 to n
when j=n-1 , k's value is not going to change right ?
i tried this by assigning n=6 and i feel whatever i say is correct ?
Is there any trick in this ?

Thanks
/Mc

hi, the soln is as follows...

• Value of i changes from 0 to n-2
• Value of j changes as follows..
  • 1 to n-1
  • 2 to n-1
  • .....
  • n-2 to n-1
• Value of k changes as follows
  • For j=1 to n-1
    • 2 to n
    • 3 to n
    • 4 to n
    • .....
    • n to n
  • for j=2 to n-1
    • 3 to n
    • 4 to n
    • ....
    • n to n
  • ......
  • for j= n-2 to n-1
    • n-1 to n
    • n to n

Thus total number of executions is summation of number of times value of k changes which is =(n-2)(n to n)+(n-2)(n-1 to n)+(n-3)(n-2 to n)....1(2 to n) =(n-2)(n to n)+(n-2)(n-1 to n)+(n-3)(n-2 to n)....1(2 to n)+0(1 to n) =(n-2)(1) + [(n-2)2+(n-3)3+......+(1)(n-1)+(0)(n)] =(n-2)(1) + [ summation of (n-i)i ] where i =2 to n =(n-2)(1) + [ summation of (n-i)i ] - n +1 where i= 1 to n the rest can be solved easily using the formulas 1+2+3....n= n(n+1)/2 1^2+2^2....n^2=(n)(n+1)(2n+1)/6

[loveleen]

I guess the problem was wrongly solved by me previously...
I have considered n to n because the computer checks even for k= n to n....and checking takes 1 step....
The soln is
J = 1 to n-1
= 2 to n-1
=
....

....
= n-1 to n-1
--------------------------------------------------------
--------------------------------------------------------
When j=1 to n-1

K = 2 to n i.e n-1 steps
= ...
= ...
= n to n i.e 1 step ... 1 step is for checking...

Total steps when j=1 to n-1 is (n-1) + (n-2) + (n-3) +....1
----------------------------------------------------------
When j=2 to n-1

K = 3 to n i.e n-2 steps
=
= ...
= n to n i.e 1 step

Total steps When j=2 to n-1 is (n-2) + (n-3) +(n-4)...+ 1
....
....
...
....
..............................................................................
When j= n-1 to n-1

K = n to n

Total steps When j= n-1 to n-1 is 1
---------------------------------------------------------------
Summation of all steps is

1X(n-1) + 2X(n-2) +3X(n-3)........(n-1)1

or

1X(n-1) + 2X(n-2) +3X(n-3)........(n-1)X(n-(n-1))

or

( n+ 2Xn + 3Xn......n-1Xn) - (1+2+3....n-1)

or

nX(1+2+3..........n-1) -(1+2+3....n-1)

or
(n-1)X(1+2+3....n-1)

or

(n-1)(n-1)(n)/2

----------------------------------------------------------