Quicksort reaches the worst-case time complexity when:
Partition is not implemented in place
Picking the largest one of input or partitioned data as pivot value
Median of input or partitioned data is expensive to calculate
Data is sorted already and always pick the median as pivot
Choose the incorrect statement:
When the median is always picked as pivot in input/partitioned data, then quicksort achieves the best-case time complexity.
Mergesort has O(N(log(N)) time complexity for its worst case, average case and best case
Insertionsort reaches its best-case time complexity O(N log(N)) when the input data is pre-sorted
Quicksort is practically fast and frequently used sorting algorithm.
Choose the incorrect statement:
In the lower bound analysis by using decision tree, each branch uses one comparison to narrow down possible cases
In the lower bound analysis by using decision tree, he number of required comparisons can be represented by height of decision tree
A decision tree to sort N elements must have N^2 leaves
O(N log(N)) lower bound means that comparison-based algorithm cannot achieve a time complexity better than O(N log(N))
Choose the incorrect statement regarding time complexity of union-find operation:
Inverse Ackermann function does not depend on N and is a constant factor.
When we use arbitrary union and simple find for union-find operation, the worst-case time complexity is O(MN) for a sequence of M operations and N elements
Union-by-size and Union-by-rank both improve the time complexity to O(M log(N)) for a sequence of M operations and N elements
To finish the entire equivalence class computation algorithm, we need to go over each pair of elements, so if we use union-by-rank with path compression for find operation, then the overall time complexity is O(N^2 log*N), where log*N denotes the inverse Ackermann function.
Choose the incorrect statement regarding Dijstraâs algorithm
Dijstraâs algorithm is a greedy algorithm
Dijstraâs algorithm requires to dynamically update distance/costs/weights of paths.
To begin with, Dijstraâs algorithm initializes all distance as INF
Dijstraâs algorithm can be implemented by heaps, leading to O(|E|+|V| log(|V|)) time complexity, where, particularly, log(|V|) is due to "insert" operation in heaps.
