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

for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++)
for(k=j+1;k<n;k++)

If only i and j loop were there the time complexity would be O(n^2-n/2) but considering the 3rd loop i got kind a lost.

3
Contributors
3
Replies
4
Views
13 Years
Discussion Span
Last Post by 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 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

hi,i have a doubt in this.

For j=1 to n-1

• 2 to n
• 3 to n
• 4 to n
• .....
• n to n

it should be like this right ?
For j=1 to n-1

• 2 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

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

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.