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)`

**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)`

**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.*