## Runtime Analysis: Big O Notation

Sometimes its a good idea to look at your code and give an idea of how well it will actually perform. We could place some timers inside of our methods that will print out how long something took to run but this will change depending on the data, what computer its performed on, etc. This means that just placing a timer doesn't really give us a lot of useful information. Also, there are special cases that can be determined that may make a certain algorithm run faster than it normally does. This also poses a significant problem with just using a timer. Big O Runtime Analysis is one way of trying to look at an algorithm and say "In worst case, it will take this long to happen with general data".

In terms of our analysis, we will be looking at how complex and algorithm is. This refers to how many times an algorithm will perform simple actions, such as comparisons, swapping items, adding, subtracting, etc. We assume that all of these simple actions will take the same amount of time to occur. We could come up with a polynomial to determine a generic runtime of our algorithm. I bet you never thought you'd hear polynomial in a programming class! Lets take a look at an example piece of code.

In terms of our analysis, we will be looking at how complex and algorithm is. This refers to how many times an algorithm will perform simple actions, such as comparisons, swapping items, adding, subtracting, etc. We assume that all of these simple actions will take the same amount of time to occur. We could come up with a polynomial to determine a generic runtime of our algorithm. I bet you never thought you'd hear polynomial in a programming class! Lets take a look at an example piece of code.

```
public void initializeArray(int[] a)
{
for(int i = 0; i < a.length; i++){
a[i] = (int)(Math.random()*101);
}
}
```

The code above will take an array that has been create with a set number of positions and fill those positions with a random number between 0 and 100. If we look at this more closely, before the loop begins, we will create a variable called i and set it equal to 0. This is a single operation. Now if we look at when we go inside of the loop, we first compare the i to the length of the array, we then generate a random number, we multiply this number by 101, and we set the array position to this number. Finally, we increment the counter i by 1. This is 4 operations that occur inside of the loop. How many times does the loop execute? Well, it goes from 0 to the end of the array. That is, it executes the same number of times as the number of items in the array. Lets call this number N. Putting this all together we get N*4 + 1. This polynomial represents the complexity of our algorithm.

Now, we need to notice that as we make the array bigger, it will take longer to run. And the bigger the array is, the more the single numbers really don't make too much of a difference. The limiting factor is the N items. This is what Big O says.

O(4*N+1) becomes O(N)

Lets look at a different algorithm. Lets look at Selection Sort for before

Now, we need to notice that as we make the array bigger, it will take longer to run. And the bigger the array is, the more the single numbers really don't make too much of a difference. The limiting factor is the N items. This is what Big O says.

O(4*N+1) becomes O(N)

Lets look at a different algorithm. Lets look at Selection Sort for before

```
public void selectionSort(int[] n){
// start at the first element and go up to the second from the end element
for (int i = 0; i < n.length - 1; i++) {
// keep track of the smallest element's position
int minPos = i;
// start at the next position in the array and go through the remaining items
for (int j = i + 1; j < n.length; j++) {
// if the current element is smaller than the minimum I have found, keep track of it instead
if (n[j] < n[minPos]) {
minPos = j;
}
}
// swap the smallest element into its proper position
int temp = n[i];
n[i] = n[minPos];
n[minPos] = temp;
}
}
```

Lets start in the first for loop. This loop runs 1 less than the number of elements in the array. That is (N-1) times. Inside of this loop, we have the creating a new variable, and the 3 swapping steps after the inner most loop. That is 4*(N-1) steps along with the inner most loop. The inner most loop is a little more tricky because we start partway through the array every time. If we think of this we start 1 more than the i and loop through N-2 items. Next time it is N-3 times. This continues over and over again because of the outer most loop. This is just an arithmetic sequence (again, more math terms!). Putting all of this together, it becomes the polynomial 4*N^2/2 +3N.

For this polynomial, as N grows bigger, the real determining factor here is the fact that we have N^2. This is what will drive the execution time up the fastest. So when we use Big O notation, Bubble Sort is O(N^2)

For this polynomial, as N grows bigger, the real determining factor here is the fact that we have N^2. This is what will drive the execution time up the fastest. So when we use Big O notation, Bubble Sort is O(N^2)

## Efficiency Chart

Below is a table to show you the different runtimes in order from fastest to slowest.