Big O
)}

# 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 SizeLoops
22
36
412
520
630

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

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