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.
So please help me!
hi,
the soln is as follows...
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
it should be like this right ?
For j=1 to n-1
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 nthe 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
----------------------------------------------------------
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.