Big-O Complexity Cheat Sheet
Uploaded by
filoyoh561Big-O Complexity Cheat Sheet
Uploaded by
filoyoh561Common questions
Powered by AIA binary heap is preferred over an unsorted array for Dijkstra's algorithm due to its efficient log-time operations for inserting and extracting the minimum, which are crucial in pathfinding. The time complexity with a binary heap is O((|V| + |E|) log |V|), versus O(|V|^2) with an unsorted array, as the latter requires linear time extraction of the smallest element, drastically increasing computational effort with larger graphs .
Dijkstra's algorithm demonstrates different time complexities depending on the priority queue data structure used. When using a binary heap, the time complexity is O((|V| + |E|) log |V|), while using a Fibonacci heap reduces it to O(|E| + |V| log |V|) because the Fibonacci heap allows more efficient decrease-key operations, which are frequent in Dijkstra's algorithm .
Merge Sort has an auxiliary space complexity of O(n) because it necessitates additional storage equivalent to the size of the array for temporary merging. QuickSort, on the other hand, requires O(log(n)) space on average for the recursive call stack if implemented in-place, making it significantly more space-efficient compared to Merge Sort in usual scenarios .
Binary Search in a sorted array has a time complexity of O(log(n)), which allows it to efficiently halve the search space with each step. In contrast, Linear Search has a time complexity of O(n), as it requires checking each element sequentially. Therefore, Binary Search is significantly more efficient for large datasets where the array is sorted .
An adjacency list stores vertices and their edges as a list, providing an efficient representation for sparse graphs with time complexities of O(|V|+|E|) for storage and O(1) for adding edges. An adjacency matrix, however, uses a two-dimensional array, which results in O(|V|^2) for storage, optimal for dense graphs, and provides constant time O(1) complexity for edge queries. The matrix can be wasteful for space, particularly for graphs with fewer edges .
Radix Sort is preferred for sorting fixed-width data types like integers when the number of elements n and range k are such that k is linear relative to n, leading to O(nk) time complexity. It efficiently sorts by processing digits or bits independently, which can outperform comparison-based sorts on narrow data types, leveraging O(n) linear operations per pass without relying on element comparisons, making it optimal for sizable uniform input distributions .
The choice of sorting algorithm heavily influences computational complexity, especially for large datasets. Algorithms like QuickSort and MergeSort with average time complexities of O(n log(n)) tend to perform better in practice for sizable data due to efficient divide-and-conquer strategies. However, QuickSort may degrade to O(n^2) in the worst case, making MergeSort preferable for consistent performance. Conversely, selection-intensive or small workload contexts may justify simpler algorithms like Insertion Sort, despite its O(n^2) complexity, due to negligible overhead .
Both Depth First Search (DFS) and Breadth First Search (BFS) have a time complexity of O(|E| + |V|) when traversing a graph with |V| vertices and |E| edges. This reflects the need to visit every vertex and edge in their respective traversal processes, making them equally efficient in terms of time complexity for graph traversal .
QuickSort has a best-case time complexity of O(n log(n)) when the pivot divides the input into two even halves at every step, achieving efficient recursive subarray sorting. However, in the worst case, such as when the smallest or largest element is consistently chosen as the pivot (common in already sorted arrays), the time complexity degrades to O(n^2) due to the lack of divide-and-conquer efficiencies .
AVL Trees are typically favored over Red-Black Trees when applications demand more frequent read or search operations due to stricter balancing, which results in faster queries. AVL Trees maintain a guarantee of stricter O(log(n)) heights, which translates to consistent and often faster search times relative to the amortized balancing of Red-Black Trees, suitable for environments prioritizing read efficiency over writes .