UCF FE Runtime Flashcards

Vocabulary flashcards covering time complexities, tree structures, heaps, sorting algorithms, linked lists, stacks, queues, hashing, and math recurrences for UCF Foundation Exam preparation.

Quicksort Runtimes

Best case: $O(n \log(n))$, Average case: $O(n \log(n))$, Worst case: $O(n^2)$.

Quicksort Worst-Case Degradation

Occurs when the pivot repeatedly creates extremely unbalanced partitions (such as sizes $n-1$ and $0$), causing the recursive work to sum to $n + (n-1) + \dots + 1 = O(n^2)$.

Merge Sort Runtimes

$O(n \log(n))$ in best, average, and worst cases.

Insertion Sort Runtimes

Best case: $O(n)$ when already sorted, Average case: $O(n^2)$, Worst case: $O(n^2)$.

Selection Sort Runtimes

$O(n^2)$ in best, average, and worst cases because it scans the unsorted portion to choose the next minimum/maximum.

Bubble Sort Runtimes

With early-exit optimization: Best case $O(n)$, Average case $O(n^2)$, Worst case $O(n^2)$. Without early exit, best case is $O(n^2)$.

Heap Sort Runtimes

$O(n \log(n))$ in best, average, and worst cases.

Guaranteed Worst-Case $O(n \log(n))$ Comparison Sorts

Merge Sort and Heap Sort. Quicksort does not guarantee this because its worst case is $O(n^2)$.

Arbitrary Binary Tree Search Runtime

Worst-case $O(n)$, because there is no ordering rule to discard a subtree.

BST Search Runtimes

Average case: $O(\log(n))$ when reasonably balanced. Worst case: $O(n)$ when degenerated into a chain.

BST Insertion Runtimes

Average case: $O(\log(n))$ when reasonably balanced. Worst case: $O(n)$ when highly skewed.

BST Deletion Runtimes

Average case: $O(\log(n))$ when reasonably balanced. Worst case: $O(n)$ where search path dominates.

AVL Tree Search Runtime

Worst-case $O(\log(n))$, because AVL balancing guarantees logarithmic height.

AVL Tree Insertion Runtime

Worst-case $O(\log(n))$, consisting of $O(\log(n))$ search down the tree and a constant number of rotations for rebalancing.

AVL Tree Deletion Runtime

Worst-case $O(\log(n))$, because the tree height is $O(\log(n))$ and updates/rebalancing occur along a root-to-leaf path.

AVL Tree Height

$O(\log(n))$ for storing $n$ items.

Balanced Tree Traversal Runtime

$O(\log(n))$ for one root-to-leaf traversal in a balanced tree with $n$ nodes.

Heap Peek Runtime

$O(1)$ to peek at the minimum in a min-heap or maximum in a max-heap because the desired element is at the root.

Binary Heap Insertion Runtime

Worst-case $O(\log(n))$ because the new item may percolate up the heap height.

Heap Min/Max Removal Runtime

Worst-case $O(\log(n))$ because the replacement root may percolate down the heap height.

Bottom-Up Heap Construction Runtime

$O(n)$ to build a heap from $n$ unsorted values, which is faster than inserting $n$ values one at a time.

Heap Construction via N Insertions Runtime

$O(n \log(n))$ to build a heap by performing $n$ separate heap insertions.

Heapify / Percolate-Down Runtime

Worst-case $O(\log(n))$ from one node in a heap.

Heap Arbitrary Search Runtime

$O(n)$ because heap order only guarantees parent-child priority without BST-style left/right ordering.

Stack Push, Pop, and Peek Runtimes

$O(1)$ each for standard array or linked-list implementations.

Consecutive Stack Pops Runtime

$O(p)$ for performing $p$ consecutive pop operations on a stack.

Queue Enqueue, Dequeue, and Front/Peek Runtimes

$O(1)$ each with a standard linked queue or circular-array queue.

Singly Linked List Kth Node Access Runtime

$O(k)$, which is worst-case $O(n)$, requiring traversal of next pointers from the front.

Linked List Fixed Position Deletion Runtime

$O(1)$ to delete the third node when the list has more than $3$ nodes because third is a fixed constant position.

Linked List Front Insertion/Deletion Runtime

$O(1)$, assuming access to the head pointer.

Linked List Search Runtime

Worst-case $O(n)$ when searching for a target value.

Hash Table Search, Insert, and Delete Runtimes

Average case: $O(1)$ with a good hash function and controlled load factor. Worst case: $O(n)$ if many keys collide or clustering becomes severe.

Hashing Comparison to BST/AVL

Usually faster than BST/AVL lookup with average $O(1)$, but unlike AVL trees, it can degrade to $O(n)$ in the worst case.

Array Access by Known Index Runtime

$O(1)$.

Linear Search Runtime

Worst-case $O(n)$ through an unsorted array of $n$ items.

Two Independent Nested Loops Runtime

$O(n^2)$ for two independent nested loops that each run $n$ times.

Logarithmic Loop Runtime

$O(\log(n))$ for a loop that repeatedly halves $n$ or doubles a counter until it reaches $n$.

Repeated Logarithmic Operation Runtime

$O(n \log(n))$ when an $O(\log(n))$ operation is repeated $n$ times.

Harmonic Sum Runtime

$O(n \log(n))$ for $n + n/2 + n/3 + \dots + n/n$, because the harmonic sum is $O(\log(n))$.

Constant Factors in Big-O

Constant factors do not change Big-O (e.g., $O(n/2) = O(n)$), though repeating $n/2$ operations $n$ times gives $O(n^2)$.

Recurrence $T(n) = T(n/2) + O(n)$ Runtime

$O(n)$, where work forms $n + n/2 + n/4 + \dots = O(n)$.

Recurrence $T(n) = 2T(n/2) + O(n)$ Runtime

$O(n \log(n))$, having $O(\log(n))$ levels and $O(n)$ work per level.

Recurrence $T(n) = T(n-1) + O(1)$ Runtime

$O(n)$, as input decreases by $1$ for about $n$ recursive calls.

Decimal to Binary Conversion Runtime

$O(\log(n))$ to convert positive integer $n$ to binary, as the number of binary digits is proportional to $\log(n)$.

Array Integer Addition Runtime

$O(\max(c,d))$ to add a $c$-digit integer to a $d$-digit integer stored digit-by-digit in arrays ($O(d)$ if $d \ge c$).