4️⃣

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

⚖️