# Problem
This function uses a nested loop to sort an array. What is the time complexity?

```python
def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
```

# Solution

| Input Size | Loops  |
| --- | --- |
| 2 | 2 |
| 3 | 6 |
| 4 | 12 |
| 5 | 20 |
| 6 | 30 |

### How does the runtime increase w.r.t. input size?

The number of loops can be expressed by the equation $N^2 - N$

### What is the time complexity?

Never try to be specific. $N^2$ dominates $N$. At first glance, it would have been enough to notice that the time complexity is proportionately quadratic to the input size $O(N^2)$.

-----
##### This workbook was created by Jad and Rayan Slim. Feel free to explore some of their courses:
##### [The Complete Java Development Bootcamp](https://udemy-redirect-app.herokuapp.com/java)
##### [The Complete Spring Boot Development Bootcamp – Become a Java Web Developer](https://udemy-redirect-app.herokuapp.com/spring)


Problem 10 Solution

Problem 12 Solution

Problem 4 Solution

Problem 8 Solution

Workbook

Problem 7 Solution

Problem 15 Solution

Problem 2 Solution

Problem 14 Solution

Problem 6 Solution

Problem 5 Solution

Problem 17 Solution

Problem 3 Solution

Problem 1 Solution

Problem 16 Solution

Problem 13 Solution

Problem 11 Solution

Problem 9 Solution

Big O