__Analyzing Selection Sort (using Big-O)__

Let’s analyze the running time of it using the method we learned in a previous section. There is no code that doesn’t run or ends prematurely so there are no tricky cases to worry about. Here is the code again.

```
arr = [1, 4, 2, 7, 7, 6] # change this array to the array you want to sort
for first_idx in range(len(arr)):
min_idx = first_idx
for second_idx in range(first_idx + 1, len(arr)):
if arr[second_idx] < arr[min_idx]:
min_idx = second_idx
arr[first_idx], arr[min_idx] = arr[min_idx], arr[first_idx]
print(arr)
```

View code on GitHub.

Line 1 is the input so it isn’t part of the running time analysis.

Line 2 is a for loop that checks all the indexes (n operations) of the list. The running time is O(n).

Line 3 is assigning a variable, which is one operation. This is always O(1).

Line 4 is a for loop that checks all the indexes of the list starting from `first_idx+1`

. This is tricky. How to find running time for a for loop whose number of iterations keeps changing throughout the program? Well, you would take the average number of iterations throughout the program. Since `first_idx`

could be the numbers from 0 to n-1, second_idx could be 1 to n-1. The average of the numbers from 1 to n-1 is 0.5n. This means there are 0.5n operations. Therefore, the running time is O(n).

Line 5 is an if statement and the condition inside takes a constant number of operations to do regardless of input. Therefore, the running time is O(1).

Line 6 is assigning a variable, which is one operation. This is always O(1).

Line 7 is tuple unpacking which takes a constant number of operations to do regardless of input. Therefore, the running time is O(1).

Line 9 we are ignoring in our analysis since it isn't part of the algorithm itself.

Let’s put the running time next to each line.

```
arr = [?, ?, ?] # this is the input, so we're not including it in analysis
for first_idx in range(len(arr)): # O(n)
min_idx = first_idx # O(1)
for second_idx in range(first_idx + 1, len(arr)): # O(n)
if arr[second_idx] < arr[min_idx]: # O(1)
min_idx = second_idx # O(1)
arr[first_idx], arr[min_idx] = arr[min_idx], arr[first_idx] # O(1)
```

Now multiply the running time of the code inside the for loop by the running time of the for loop. Let’s start with the inner for loop.

```
arr = [?, ?, ?] # this is the input, so we're not including it in analysis
for first_idx in range(len(arr)): # O(n)
min_idx = first_idx # O(1)
for second_idx in range(first_idx + 1, len(arr)): # O(n)
if arr[second_idx] < arr[min_idx]: # O(1) * O(n) = O(n)
min_idx = second_idx # O(1) * O(n) = O(n)
arr[first_idx], arr[min_idx] = arr[min_idx], arr[first_idx] # O(1)
```

Then let’s do it for the outer loop.

```
arr = [?, ?, ?] # this is the input, so we're not including it in analysis
for first_idx in range(len(arr)): # O(n)
min_idx = first_idx # O(1) * O(n) = O(n)
for second_idx in range(first_idx + 1, len(arr)): # O(n) * O(n) = O(n^2)
if arr[second_idx] < arr[min_idx]: # O(1) * O(n) * O(n) = O(n^2)
min_idx = second_idx # O(1) * O(n) * O(n) = O(n^2)
arr[first_idx], arr[min_idx] = arr[min_idx], arr[first_idx] # O(1) * O(n) = O(n)
```

After we calculated the running time of all the lines of code, let’s add them up.

```
arr = [?, ?, ?] # this is the input, so we're not including it in analysis
for first_idx in range(len(arr)): # O(n)
min_idx = first_idx # O(1) * O(n) = O(n)
for second_idx in range(first_idx + 1, len(arr)): # O(n) * O(n) = O(n^2)
if arr[second_idx] < arr[min_idx]: # O(1) * O(n) * O(n) = O(n^2)
min_idx = second_idx # O(1) * O(n) * O(n) = O(n^2)
arr[first_idx], arr[min_idx] = arr[min_idx], arr[first_idx] # O(1) * O(n) = O(n)
# Sum = O(n) + O(n) + O(n^2) + O(n^2) + O(n^2) + O(n)
# Sum = 3*O(n) + 3*O(n^2)
```

After we add them up, we eliminate the constants and the lower-order terms.

```
arr = [?, ?, ?] # this is the input, so we're not including it in analysis
for first_idx in range(len(arr)): # O(n)
min_idx = first_idx # O(1) * O(n) = O(n)
for second_idx in range(first_idx + 1, len(arr)): # O(n) * O(n) = O(n^2)
if arr[second_idx] < arr[min_idx]: # O(1) * O(n) * O(n) = O(n^2)
min_idx = second_idx # O(1) * O(n) * O(n) = O(n^2)
arr[first_idx], arr[min_idx] = arr[min_idx], arr[first_idx] # O(1) * O(n) = O(n)
# Sum = O(n) + O(n) + O(n^2) + O(n^2) + O(n^2) + O(n)
# Sum = 3*O(n) + 3*O(n^2)
# Final Running Time = O(n^2)
```

View code on GitHub.

__Previous Section__

__Next Section__

**Copyright © 2021 Code 4 Tomorrow. All rights reserved.**
The code in this course is licensed under the MIT License.
*If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact **classes@code4tomorrow.org** for inquiries.*