# Thread: Help with Big O notation

1. Member
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 < length-1-y; 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]);
}
}

2. Member
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

3. ## Re: Help with Big O notation

Originally Posted by mxcnrawker
- all loops are O(n)
A O(log(n)) loop:

Java Code:
`for (int i= 1; (i<<= 1) < n; ) ...`
A O(n*n) loop:

Java Code:
`for (int i= 1; i < n*n; i++ ) ...`
etc. etc.

kind regards,

Jos

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.

#### Posting Permissions

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