# Help with Big O notation

• 12-10-2012, 08:39 AM
Steve911
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]);
}
}
• 12-10-2012, 09:16 AM
mxcnrawker
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
• 12-10-2012, 11:36 AM
JosAH
Re: Help with Big O notation
Quote:

Originally Posted by mxcnrawker
- all loops are O(n)

A O(log(n)) loop:

Code:

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

Code:

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

kind regards,

Jos
• 12-10-2012, 07:27 PM