Results 1 to 10 of 10
 09162011, 04:24 AM #1Member
 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; 09162011 at 04:37 AM.
 09162011, 04:39 AM #2
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
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.
 09162011, 04:45 AM #3Member
 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 ???
 09162011, 04:47 AM #4
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
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.
 09162011, 04:48 AM #5Member
 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; 09162011 at 04:56 AM.
 09162011, 04:49 AM #6Member
 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.
 09162011, 04:55 AM #7
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
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); }
 09162011, 05:08 AM #8Member
 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); } }
Last edited by lulzim; 09162011 at 05:22 AM.
 09162011, 03:47 PM #9
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
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.
 09162011, 04:51 PM #10Moderator
 Join Date
 Jul 2010
 Location
 California
 Posts
 1,641
 Rep Power
 7
Re: I need help for Time Complexity of this???
Crossposted I need help for this time complexity measurment?
Similar Threads

Linked List, Array List time complexity
By Rick99771977 in forum New To JavaReplies: 4Last Post: 08182011, 06:37 AM 
Time complexity  foor loop
By hawaiifiver in forum New To JavaReplies: 5Last Post: 02052011, 05:06 PM 
time complexity questions
By myst in forum New To JavaReplies: 6Last Post: 07132010, 12:02 PM 
Time Complexity Java Code?
By Lyricid in forum New To JavaReplies: 11Last Post: 12082009, 05:27 PM 
Please tell me I am not crazy... Time Complexity (BigO) Question
By Jordan in forum New To JavaReplies: 2Last Post: 11042008, 03:48 AM
Bookmarks