|
Big Oh Notation
Best, Average and Worse Cases
The relationship between the number of 'operations' (n) and the Big Oh of the algorithm can easily be seen in the chart below.
| | constant | logarithmic | linear | | quadratic | cubic |
|---|
| n | O(1) |
O(log N) |
O(N) |
O(N log N) |
O(N2)
| O(N3) |
|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |
| 1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 | 1016 |
Big Oh of Common Searching Algorithms
| Search Type |
Big-Oh | Comments |
| Linear search array/ArrayList/LinkedList | O(N) | |
| Binary search sorted array/ArrayList | O(log N) |
data must already be sorted. |
| Search balanced tree | O(log N) | |
| Search hash table | O(1) | |
Other common
| Algorithm | array
ArrayList | LinkedList |
|---|
| access front | O(1) | O(1) |
| access back | O(1) | O(1) |
| access middle | O(1) | O(N) |
| insert at front | O(N) | O(1) |
| insert at back | O(1) | O(1) |
| insert in middle | O(N) | O(1) |
Big Oh of Common Sorting Algorithms
By best, worst and average case for well known sorting algorithms. Animated Demonstration of Sorting Algorithms
| Type of Sort | Best | Worst | Average |
|---|
| BubbleSort | O(N) |
O(N2) |
O(N2) |
| Insertion sort | O(N) (best beats Selection) | O(N2) | O(N2) |
| Selection sort | O(N2) | O(N2) | O(N2) |
| QuickSort | O(N log N) | O(N2) | O(N log N) |
| HeapSort | O(N log N) | O(N log N) | O(N log N) |
| MergeSort | O(N log N) | O(N log N) | O(N log N) |
Practice Big-Oh Problems
Look at each code fragment below and determine its Big-Oh notaiton. (The first three problems are taken from Fran Trees powerpoint on Big-Oh Notation)
Practice Problem 1)
What is the Big-Oh of the code below?
//CODE
int sum = 0;
for(int c=1; c<=n; c++)
for (int c2=1; c2<=n; c2++)
sum += c*c2;
|
This fragment is O(n²) since for each n we have two loops that count up to the given 'n'. Consider when n is 10 for instance: the outer loop counts from 1 to 10 and the inner loop also counts from 1 to 10 − (each time summing the product of the current value of c1 and c2).
|
Practice Problem 3)
What is the Big-Oh of the code fragment below?
//pre-condition : n >= 2
public int doSomething(int n){
int r = 1;
for(int m = 1 ;m < n; m++){
r *= m + 5;
}
return r;
}
|
The Big-Oh ofthis methos is O(n) because for any given value of n our loop will visit all numbers from 1 to that particular n (performing an addition on each) and then add 5. O(n +5) has the same order as O(n) . Remember Big-Oh is ruled by the order of magnitude of the largest term which in this case is n.
|
Practice Problem 4)
What is the Big-Oh of the code fragment below?
//pre-condition : n >= 2
public int doSomething2(int n){
int r = 1;
for(int m = 1 ;m < n; m++){
r *= m;
r -= 90;
r /= 3;
}
return r;
}
|
Like the problem before, this is O(n) because O(3n) has an order of magnitude of n...forget about the coefficient '3'. This method might perform 3 operations but it does that 'n' times! |
Practice Problem 5)
What is the Big-Oh run time of the code below?
You can assume that the myArray1 contains elements myArray1[0], myArray1[1], myArray1[2].... myArray1[m-1] where m = myArray1.length.
int counter=0;
for(int i=0;i < m ; i++){
if(myArray1[i] != 0 )
{
myArray1[counter]= myArray1[i];
counter++;
}
int[] myArray2;
myArray2 = new int[counter];
for(int i=0;i< counter; i++)
myArray2[i] = myArray1[i];
|
This is O(n). This fragment creates a second array, myArray2, by taking all of the non-zeros from the first array,myArray1. Now, the absolute worst case of this would be if all of the elements in myArray1 were non-zeros. In that case, you would have O(2n) since you'd loop over every element twice...but we ignore co-efficients so, even in the worst case scenario, this is still O(n) or linear.
|
Practice Problem 6)
The problem below refers to AP Computer Science's Grid World Case Study.
What is the Big-Oh of the Grid method ArrayList<Location>
getOccupiedLocations(). If you recall, this method returns an ArrayList of all the locations that are occupied. This method performs a nested loop based on the number of rows and the number of columns. This question assumes a BoundedGrid that has R rows and C columns.
|
Although you might be tempted to think that this method has a Big-Oh of O(N²) this case would only be true IF the number of rows equals the number of columns and the BoundedGrid was actually a perfect square. The true answer is that the Big-Oh O(R*C) |
Top
|
