# Problem

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

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

##### The Complete Spring Boot Development Bootcamp – Become a Java Web Developer

Feedback Summary

0.0

0 students

5

0%

4

0%

3

0%

2

0%

1

0%

Written Reviews

There are no written reviews yet.