Help with Big O notation

[Steve911]

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]);
}
}

[mxcnrawker]

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

[JosAH]

- all loops are O(n)

A O(log(n)) loop:

for (int i= 1; (i<<= 1) < n; ) ...

A O(n*n) loop:

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

etc. etc.

kind regards,

Jos

[quad64bit]

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)

is misleading.

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.