Help with JAVA

I've heard conversation coming out of animal pens that is more intelligent than what is going on in here.
INVADEtheLINE
Posts: 552
Joined: Tue Mar 25, 2008 1:29 am
Team: Privateer
Location: New York, NY
Contact:

Help with JAVA

Postby INVADEtheLINE » Mon Feb 20, 2012 8:57 pm

So I was given these 2 questions about a worst-case big-Oh analysis. I'm just learning Java, so I need help understanding lol.

Code: Select all

for (int i = 0; i < n; i++)
{
          for (int j = 0; j < 2*n; j++)
          {
                    System.out.println ("Hello!");
           }
}


and

Code: Select all

for (int i = 0; i < n; i++)
{
         for (int k = 1; k < n; k*=2)
         {
                   System.out.println("Hello!");
          {
}


So my question is- what's the wrst case analysis, and why? Very brief is fine. I'm taking the class online and have just been crazy busy. Any help is appreciated!

User avatar
wheels1758
Posts: 4130
Joined: Tue Oct 21, 2008 5:20 pm
Location: Washington, USA
Contact:

Re: Help with JAVA

Postby wheels1758 » Mon Feb 20, 2012 10:23 pm

INVADEtheLINE wrote:So I was given these 2 questions about a worst-case big-Oh analysis. I'm just learning Java, so I need help understanding lol.

Code: Select all

for (int i = 0; i < n; i++)
{
          for (int j = 0; j < 2*n; j++)
          {
                    System.out.println ("Hello!");
           }
}


and

Code: Select all

for (int i = 0; i < n; i++)
{
         for (int k = 1; k < n; k*=2)
         {
                   System.out.println("Hello!");
          {
}


So my question is- what's the wrst case analysis, and why? Very brief is fine. I'm taking the class online and have just been crazy busy. Any help is appreciated!


Correct me if I'm wrong but a for loop is O(N). So this nested for loop is (N^2). Big O for outer is O(N). Big O for inner is O(2N). So O(N * 2N) = O(N^2) dropping the constant.

For #2:
Outer loop is again O(N). inner loop is now O((N-1) / 2), or O(N/2). so O(N * (N/2)) is again O(N^2) because you get rid of the constant.

Again, its been a while since I've done these, but I think that is correct...

jlv
Site Admin
Posts: 13461
Joined: Fri Nov 02, 2007 5:39 am
Team: No Frills Racing
Contact:

Re: Help with JAVA

Postby jlv » Tue Feb 21, 2012 1:10 am

The second inner loop is log2(n). "k" doubles on every iteration.
Josh Vanderhoof
Sole Proprietor
jlv@mxsimulator.com
If you email, put "MX Simulator" in the subject to make sure it gets through my spam filter.

User avatar
wheels1758
Posts: 4130
Joined: Tue Oct 21, 2008 5:20 pm
Location: Washington, USA
Contact:

Re: Help with JAVA

Postby wheels1758 » Tue Feb 21, 2012 1:15 am

jlv wrote:The second inner loop is log2(n). "k" doubles on every iteration.


Ahh good catch! K *= 2 is a bit different that K+=2. OOPS! :lol:

INVADEtheLINE
Posts: 552
Joined: Tue Mar 25, 2008 1:29 am
Team: Privateer
Location: New York, NY
Contact:

Re: Help with JAVA

Postby INVADEtheLINE » Tue Feb 21, 2012 1:32 pm

Thanks a bunch guys- I got the first one without an issue, but made the same mistake wheels did for the 2nd fragment. Since the class is just starting, it's fairly easy to try and teach myself a little on the side..thanks again!


Return to “Off Topic”

Who is online

Users browsing this forum: No registered users and 6 guests