Sorting and Patterning Searching Algorithms Time Complexity and more

Bubble Sort Best Case Big O

O(n)

Bubble Sort Average Case Big O

O(n²)

Bubble Sort Worst Case Big O

O(n²)

Bubble Sort: Stable?

Yes.

Bubble Sort Adaptable?

Yes

Bubble Sort: In/out of place?

In

Insertion Sort Best Case Big O

O(n)

Insertion Sort Average Case Big O

O(n²)

Insertion Sort Worst Case Big O

O(n²)

Insertion Sort: Stable?

Yes

Insertion Sort Adaptable?

Yes

Insertion Sort In/out of place?

In

Cocktail Shaker Sort Best Case Big O

O(n)

Cocktail Shaker Sort Average Case Big O

O(n²)

Cocktail Shaker Sort Worst Case Big O

O(n²)

Cocktail Shaker Sort: Stable?

Yes

Cocktail Shaker Sort: Adaptable?

Yes

Cocktail Shaker Sort: In/out of place?

In

Selection Sort Best Case Big O

O(n²)

Selection Sort Average Case Big O

O(n²)

Selection Sort Worst Case Big O

O(n²)

Selection Sort: Stable?

No

Selection Sort: Adaptable?

No

Selection Sort: In/out of place?

In

QuickSort Best Case Big O

O(n log n)

QuickSort Average Case Big O

O(n log n)

QuickSort Worst Case Big O

O(n²)

QuickSort: Stable?

No

QuickSort: Adaptable?

No

QuickSort: In/out of place?

In

QuickSelect Best Case Big O

O(n)

QuickSelect Average Case Big O

O(n)

QuickSelect Worst Case Big O

O(n²)

QuickSelect: Stable?

No

QuickSelect: In/out of place

In

QuickSelect: Adaptable?

Trick Question!! Adaptability only applies to sorting algorithms and this isn't a sorting algorithm.

MergeSort Best Case Big O

O(n log n)

MergeSort Average Case Big O

O(n log n)

MergeSort Worst Case Big O

O(n log n)

MergeSort: Stable?

Yes

MergeSort: Adaptable?

No

MergeSort: In/out of place?

Out

HeapSort Best Case Big O

O(n log n)

HeapSort Average Case Big O

O(n log n)

HeapSort Worst Case Big O

O(n log n)

HeapSort: Stable?

No

HeapSort: Adaptable?

No

HeapSort: In/out of place?

Out

LSD Radix Sort Best Case Big O

O(kn)

LSD Radix Sort Average Case Big O

O(kn)

LSD Radix Sort Worst Case Big O

O(kn)

LSD Radix Sort: Stable?

Yes

LSD Radix Sort: Adaptable?

No

LSD Radix Sort: In/out of place?

Out

Brute Force Best Case Big O

O(m)

Brute Force Best Case Big O - no match

O(n)

AVL Tree Insertion, Search, and Deletion Best Case Big O

Insertion - O(log n)

Search - O(1)

Deletion - O(log n)

AVL Tree Insertion, Search, and Deletion Average Case Big O

O(log n)

Balanced AVL Tree Insertion, Search, and Deletion Worst Case Big O

O(log n)

Brute Force Average Case Big O

O(mn)

Brute Force Worst Case Big O

O(mn)

Unbalanced AVL Tree Insertion, Search, and Deletion Worst Case Big O

O(n)

Last Occurrence Table Creation Best Case Big O

O(m)

Last Occurrence Table Creation Average Case Big O

O(m)

Last Occurrence Table Creation Worst Case Big O

O(m)

BoyerMoore Best Case Big O - All occurrences

O(m + n/m)

BoyerMoore Best Case Big O -Single occurrence

O(m)

BoyerMoore Worst Case Big O - All occurrences

O(mn)

BoyerMoore Average Case Big O - All occurrences

O(m + n)

Failure Table Creation Best Case Big O

O(m)

Failure Table Creation Average Case Big O

O(m)

Failure Table Creation Worst Case Big O

O(m)

KMP Main Algorithm Big O

O(n)

KMP Best Case Big O - Single Occurrence

O(m)

KMP Best Case Big O - All Occurrences

O(m + n)

KMP Worst Case Big O

Failure Table Creation - O(m)

Main Algorithm - O(n)

So, the worst case is:

O(m + n)

Rabin-Karp Best Case Big O - All Occurrences

Calculating Initial Hashes - O(m)

Searching and Updating - O(n)

So, the best case is:

O(m + n)

Rabin-Karp Best Case Big O - Single Occurrence

O(m)

Rabin-Karp Worst Case Big O

O(mn)

BoyerMoore Galil Rule Best Case Big O

O(n/m)

BoyerMoore Galil Rule Average Case Big O

O(n)

BoyerMoore Galil Rule Worst Case Big O

O(n + m)

Linear probobing (Hashmap) Insertion, Search, and Deletion Best Case Big O

O(1)

Linear probobing (Hashmap) Insertion, Search, and Deletion Average Case Big O

O(1/(1-LF))

Current Load Factor, not MAX load factor

Linear probobing (Hashmap) Insertion, Search, and Deletion Worst Case Big O

O(n)

In-Place Sorts Definition

This means that the elements in the array passed in SHOULD NOT get copied over to another data structure.

Note that you can still create variables that hold only one item, but you cannot create another data structure such as an array or list in the method.

PS. Out of place Sorts just means the opposite of in place Sorts.

Stable Sorts Definition

This means that duplicates must remain in the same relative positions after sorting as they were before sorting. Basically, saying that they are not interchangeable cuz they are duplicates and need to keep their greater or less than status before sorting, through out sorting, and after sorting.

Ex: say we have a list = [1,5a,2,4,3,5b,8, 6,7]. Disclaimer: the letters on the 5’s are just to show they are different and the letters are not actually present in the array.

Before Sorting: [1,5a,2,4,3,5b,8,6,7].

After Sorting : [1,2,3,4,5a,5b,6,7,8]

Adaptive Sorts Definition

This means that the algorithm takes advantage of existing order in the input array by not comparing elements that are already ordered/relatively sorted.

Right Rotation Requirements

1. Parent node balance factor is 2

2. Heavier Child: Left

3. Child balance factor is 1,0.

4. Rotation Shape is a branch of three nodes facing right.

AVL Left-Right Rotation Requirements

1. Parent node balance factor is 2.

2. Heavier Child: Left

3. Child balance factor is -1

4. Rotation Shape looks like a greater than symbol created by connecting three nodes.

AVL Left Rotation Requirements

1. Parent node balance factor is -2.

2. Heavier Child: Right

3. Child balance factor is -1, 0.

4. Rotation Shape is a branch of three nodes facing left.

AVL Right-Left Rotation Requirements

1. Parent node balance factor is -2.

2. Heavier Child: Right

3. Child balance factor is 1.

4. Rotation Shape looks like a less than symbol created by connecting three nodes.