# I need help for Time Complexity of this???

• 09-16-2011, 03:24 AM
lulzim
I need help for Time Complexity of this???
Does anyone knws what is the time complexity of this implementation I need O(?)

Code:

```for(int i= 0,j= 0; i< n; i++,j++ ) {   for(int a= 0,b= 0; a< n; a++,b++ )   {                                  1 statement goes  here...                              }                 }```

Is this O(n2) or O(n4) im doubting on this.

Does anybody of u can convince me in this??
• 09-16-2011, 03:39 AM
sunde887
Re: I need help for Time Complexity of this???
Why not set the value of n to some small number and do this in your head? This will help you convince yourself, how many times will it execute if n is 3?

Beware of shadowing variables in the outer loop, it can cause some confusion. After trying this for 3, if you can't find the pattern, try it with n=2,4,5 and see if a pattern appears.
• 09-16-2011, 03:45 AM
lulzim
Re: I need help for Time Complexity of this???
so i was asking from u guys to make me sure for that bc i said im doubting is it O(N2) or ???
• 09-16-2011, 03:47 AM
sunde887
Re: I need help for Time Complexity of this???
Why do you doubt it? After testing for n=2,3, and 4, this should be obvious.
• 09-16-2011, 03:48 AM
lulzim
Re: I need help for Time Complexity of this???
hehe would u have mentioned O(?) :P
• 09-16-2011, 03:49 AM
lulzim
Re: I need help for Time Complexity of this???
I mean can u explain step by step how it comes to O(?) actually if i knew i wouldnt ask about this :S.
• 09-16-2011, 03:55 AM
sunde887
Re: I need help for Time Complexity of this???
Add this to your inner loop: 'System.out.println("Count");' then run the program and count how many times 'Count' is displayed: this number should show a pattern if you change n around a bit(try n=2,3,4).

Code:

```int count = 0; for(int n = 0; n < 3;++n){   count=0;   for(int i = 0; i < n; ++i)     for(int j = 0; j < n; ++j)       System.out.println(++count); }```
This may help.
• 09-16-2011, 04:08 AM
lulzim
Re: I need help for Time Complexity of this???
Code:

```for(int SmallMatrixStartRow = 0,MainMatrixStartROW = startROW ; SmallMatrixStartRow < sizeOfMatrixPart; SmallMatrixStartRow++,MainMatrixStartROW++ ){                           for(int SmallMatrixStartColumn = 0, MainMatrixStartColumn = startColumn ; SmallMatrixStartColumn < sizeOfMatrixPart ; MainMatrixStartColumn++, SmallMatrixStartColumn++){                                                         //    Bpart.setElementAt(B.getElementAt(MainMatrixStartROW, MainMatrixStartColumn), SmallMatrixStartRow, SmallMatrixStartColumn);                                                         DestinationMatrix.setElementAt(SourcePart.getElementAt(SmallMatrixStartRow, SmallMatrixStartColumn), MainMatrixStartROW, MainMatrixStartColumn);                               }                   }```
So this is O(n2) right???
• 09-16-2011, 02:47 PM
sunde887
Re: I need help for Time Complexity of this???
Yes O(n^2), since the inner and outer loop has n as the condition it will go until. Since the inner loop will loop n times for every cycle of the outer loop, it makes sense to readon that it does n*n, or n^2.
• 09-16-2011, 03:51 PM
doWhile
Re: I need help for Time Complexity of this???