UCF Foundation Exam (Pass or Die Edition)

Best Runtime of Bubble Sort

O(n)

Worst Runtime of Bubble Sort

O(n^2)

Average Runtime of Bubble Sort

O(n^2)

Best Runtime of Selection Sort

O(n^2)

Worst Runtime of Selection Sort

O(n^2)

Average Runtime of Selection Sort

O(n^2)

Best Runtime of Insertion Sort

O(n)

Worst Runtime of Insertion Sort

O(n^2)

Average Runtime of Insertion Sort

O(n^2)

Worst & Average Runtime of Linear Probing, Quadratic Probing, and Separate Chaining Insertion

Worst = O(n)

Average = O(1)

Worst & Average Runtime of Linear Probing, Quadratic Probing, and Separate Chaining Search/Retrieval

Worst = O(n)

Average = O(1)

Equation for Linear Probing

index = (hVal + i) % h->TABLE_SIZE;

Equation for Quadratic Probing

index = (hVal + i * i) % h->TABLE_SIZE;

Worst & Best Runtimes for Trie Insertion

O(k)

Worst & Best Runtimes for Trie Search

Worst = O(k)

Best = O(1)

Worst & Best Runtimes for Trie Deletion

Worst = O(k)

Best = O(1)

Worst Case Runtimes for AVL Tree Search, Insertion and Deletion

O(log n)

Worst Case Runtimes for BST Search, Insertion, and Deletion

O(n)

Best Case Runtime for BST Search, Insertion, and Deletion

O(log n)

Best Case Runtimes for AVL Tree Search, Insertion and Deletion

O(log n)

What type of data structure works best for merge sort?

Linked Lists

What is the best, average, and worst runtimes for Merge Sort?

O(n log n)

What is the pattern for INORDER tree traversals?

Left

Root

Right

What is the pattern for PREORDER tree traversals?

Root

Left

Right

What is the pattern for POSTORDER tree traversals?

Left

Right

Root