Results 1 to 4 of 4
Thread: Help with Big O notation
 12102012, 08:39 AM #1Member
 Join Date
 Dec 2012
 Posts
 1
 Rep Power
 0
Help with Big O notation
I must learn how to find the Big O notation for 10 codes as the following:
2 minutes/question. what is a good technique to do so? what is the Big O'notation for the following code?
Give the Big O notation for the following function.
public static void notationFunction(int arr[], int length)
{
System.out.println(“\nThis function is sweet”);
for(int i = 0;i<length;i++)
{
System.out.println(“Arr[“ + i + “] = “ + arr[i]);
}
System.out.println(“Is this function order N?”);
System.out.println(“maybe...”);
for (int i = 0;i<100000;i++)
{
System.out.println(“Arr[“ + 0 + “] = ” + arr[0]);
}
for(int i = 0;i<length;i++)
{
for(int j = 0;j<length;j++)
{
System.out.println(“stuff”);
}
}
int temp;
for ( int j = 0; j < length; j++ )
for(int y=0; y < length; y++)
{
for ( int k =0; k < length1y; k++ )
if(arr[k]>arr[k+1])
{
temp = arr[k+1];
arr[k+1] = arr[k];
arr[k] = temp;
}
}
for(int i = 0;i<length;i++)
{
System.out.println(“Arr[“ + i + “] = “ + arr[i]);
}
}
 12102012, 09:16 AM #2Member
 Join Date
 Apr 2012
 Location
 San Jose Ca
 Posts
 16
 Rep Power
 0
Re: Help with Big O notation
first, you need to wrap the code
[CODE]
......
[CODE]
so we can throughly read it and give you pointers, but the best things in general:
 all primitive statements: prints are all O(1)
 all loops are O(n)
 all nested loops are O(n * m *...*q); where n,n,...q could be any variable, if they are all the same iterations then O(n**k) where k is a power := number of loops
NOTE: assuming the loops go through the entire list
else:
O(k) where k is a positive integer, which is the number of iterations it goes through
just practice and check out videos online or check your discrete mathematics book for references. Good luck
 12102012, 11:36 AM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,729
 Blog Entries
 7
 Rep Power
 21
 12102012, 07:27 PM #4
Re: Help with Big O notation
Also, even something as trivial as a print can be something other than O(1) if the thing being printed is the result of a method which is not O(1). I assume you meant printing things like strings, but a blanket statement like
prints are all O(1)
OP, this looks like a homework dump. Figuring this stuff out is the assignment, and usually needs to be done by hand. You need to derive a basic formula for the number of times something happens in a code block and simplify that to big oh notation.
mxcnrawker hinted at the basic idea, and Jos pointed out some of the great examples of where general rules fail.
You need to look at the input and outputs of the code block and see how often something is actually happening.
Similar Threads

The Big O Notation
By dougie1809 in forum New To JavaReplies: 13Last Post: 04232012, 10:39 PM 
BigO Notation
By kraigballa in forum New To JavaReplies: 9Last Post: 02232012, 03:17 AM 
+= notation
By sehudson in forum New To JavaReplies: 2Last Post: 03112011, 05:51 AM 
Big O notation
By simorgh in forum Advanced JavaReplies: 18Last Post: 07102010, 04:26 PM 
Big O Notation
By dsym@comcast.net in forum New To JavaReplies: 1Last Post: 02212009, 07:02 PM
Bookmarks