Results 1 to 10 of 10
  1. #1
    lulzim is offline Member
    Join Date
    Feb 2011
    Posts
    44
    Rep Power
    0

    Default 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. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #3
    lulzim is offline Member
    Join Date
    Feb 2011
    Posts
    44
    Rep Power
    0

    Default 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. #4
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #5
    lulzim is offline Member
    Join Date
    Feb 2011
    Posts
    44
    Rep Power
    0

    Default 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. #6
    lulzim is offline Member
    Join Date
    Feb 2011
    Posts
    44
    Rep Power
    0

    Default 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. #7
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #8
    lulzim is offline Member
    Join Date
    Feb 2011
    Posts
    44
    Rep Power
    0

    Default 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. #9
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #10
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

Similar Threads

  1. Linked List, Array List time complexity
    By Rick99771977 in forum New To Java
    Replies: 4
    Last Post: 08-18-2011, 05:37 AM
  2. Time complexity - foor loop
    By hawaiifiver in forum New To Java
    Replies: 5
    Last Post: 02-05-2011, 04:06 PM
  3. time complexity questions
    By myst in forum New To Java
    Replies: 6
    Last Post: 07-13-2010, 11:02 AM
  4. Time Complexity Java Code?
    By Lyricid in forum New To Java
    Replies: 11
    Last Post: 12-08-2009, 04:27 PM
  5. Replies: 2
    Last Post: 11-04-2008, 02:48 AM

Posting Permissions

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