Help with JAVA

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

Help with JAVA

Post by INVADEtheLINE »

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!
wheels1758
Posts: 4132
Joined: Tue Oct 21, 2008 5:20 pm
Location: Washington, USA
Contact:

Re: Help with JAVA

Post by wheels1758 »

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: 14914
Joined: Fri Nov 02, 2007 5:39 am
Team: No Frills Racing
Contact:

Re: Help with JAVA

Post by jlv »

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.
wheels1758
Posts: 4132
Joined: Tue Oct 21, 2008 5:20 pm
Location: Washington, USA
Contact:

Re: Help with JAVA

Post by wheels1758 »

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

Post by INVADEtheLINE »

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!
Post Reply