Algorithms MidTerm

Asymptotic Notation - Big-O (O)

Upper bound. f(n) = O(g(n)) means f(n) <= c * g(n) for large enough n.

Asymptotic Notation - Omega (\Omega)

Lower bound. f(n) = \Omega(g(n)) means f(n) >= c * g(n) for large enough n.

Asymptotic Notation - Theta (\Theta)

Tight bound. f(n) = \Theta(g(n)) means f(n) is both O(g(n)) and \Omega(g(n)).

Data Structures - Array Access

O(1) time complexity to access the i-th element using direct index lookup.

Data Structures - Linked List Access

O(n) worst-case time complexity to access the i-th element because you must traverse from the head node one by one.

Min-Heap Property

The key stored at each node is less than or equal to the keys of its children. The smallest element is always at the root.

Complete Binary Tree Array Indexing

For a node at index i (1-indexed): Left child = 2i, Right child = 2i + 1, Parent = \lfloor i/2 \rfloor.

Min-Heap - 3rd Smallest Element

O(1) time complexity because the candidates are strictly limited to the root's children and the children of the 2nd smallest element in a fixed complete layout.

Min-Heap Verification Algorithm

Checking if a complete binary tree stored in an array is a valid min-heap requires verifying internal nodes (indices 1 to \lfloor n/2 \rfloor), running in O(n) worst-case time.

Binary Search Trees - Degenerate Tree Height

A tree where every node's left child is NIL has a height of n - 1 and a worst-case find operation runtime of O(n).

Binary Search Trees - Tree Size Recursive Algorithm

SIZE(x): returns 0 if x == nil, else returns 1 + SIZE(x.left) + SIZE(x.right). Worst-case and best-case runtime is O(n) since every node is visited once.

Red-Black Trees

Self-balancing binary search trees that guarantee no root-to-leaf path is more than twice as long as another, ensuring O(\log n) search, insert, and delete operations.

Quicksort - Worst-Case Running Time

O(n^2) time complexity, which occurs when the input array is already sorted or when all elements have the same value.

Quicksort - Average-Case Running Time

O(n \log n) time complexity.

Counting Sort

A non-comparative sorting algorithm running in O(n + k) time, where n is the number of elements and k is the range of input values.

Radix Sort

Sorts integer data by grouping keys by individual digits, running in O(d(n + k)) time where d is the number of digits.

Horner's Rule - Polynomial Evaluation

COMPUTEPOLY(C, n, v) evaluates a polynomial efficiently in a loop using y = y * v + c[n - i] with a runtime of O(n).

Tries (Retrieval Trees)

Tree-like data structures for storing strings where searching for a string of length m takes O(m) time, independent of the total number of stored strings.