Thread: I need help for Time Complexity of this???

1. Member
Join Date
Feb 2011
Posts
44
Rep Power
0

I need help for Time Complexity of this???

Does anyone knws what is the time complexity of this implementation I need O(?)

XML 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??
Last edited by lulzim; 09-16-2011 at 03:37 AM.

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

3. Member
Join Date
Feb 2011
Posts
44
Rep Power
0

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 ???

4. 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.

5. Member
Join Date
Feb 2011
Posts
44
Rep Power
0

Re: I need help for Time Complexity of this???

hehe would u have mentioned O(?) :P
Last edited by lulzim; 09-16-2011 at 03:56 AM.

6. Member
Join Date
Feb 2011
Posts
44
Rep Power
0

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.

7. 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).

Java 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.

8. Member
Join Date
Feb 2011
Posts
44
Rep Power
0

Re: I need help for Time Complexity of this???

XML 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???
Last edited by lulzim; 09-16-2011 at 04:22 AM.

9. 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.

10. Moderator
Join Date
Jul 2010
Location
California
Posts
1,641
Rep Power
9

Re: I need help for Time Complexity of this???

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•