39 lines
1.4 KiB
Markdown
39 lines
1.4 KiB
Markdown
# Computational Complexity
|
|
|
|
## 1. Bubble Sort
|
|
|
|
### a. Best Case
|
|
|
|
The best case scenerio for the Bubble Sort is $O(n)$. This happens when the inputed list is already ordered.
|
|
|
|
ex: list = [1,2,6,8,13,34,75,88,91,100]
|
|
|
|
In this case, bubble sort will go through the array once, comparing each neighbor pair, but not changing any of the values.
|
|
|
|
### b. Worst Case
|
|
|
|
The worst case scenerio for the Bubble Sort is $O(n^2)$.
|
|
This happens when the inputed list is already ordered, but in the reverse.
|
|
|
|
ex: list = [100,91,88,,75,34,13,8,6,2,1]
|
|
|
|
In this case, bubble sort will have to move every number from their position to last position - their curent position,going through the list $\frac{n*(n-1)}{2}$ times in the procces.
|
|
|
|
## 2. Strand Sort
|
|
|
|
### a. Best Case
|
|
|
|
The best case scenerio for the Strand Sort is $O(n)$. This happens when the inputed list is already ordered.
|
|
|
|
ex: list = [1,2,6,8,13,34,75,88,91,100]
|
|
|
|
This way, every element of the initial list gets transfered to the auxiliary list in the first passing, afterwards merging with the final list.
|
|
|
|
### b. Worst Case
|
|
|
|
The worst case scenerio for the Strand Sort is $O(n^2)$.
|
|
This happens when the inputed list is already ordered, but in the reverse.
|
|
|
|
ex: list = [100,91,88,,75,34,13,8,6,2,1]
|
|
|
|
This way, only one element gets transfered to the auxiliary list each passing of the initial list. Strand sort will have to pass through the initial list $\frac{n*(n-1)}{2}$ times. |