The problem of determining if a context-free grammar (CFG) generates all strings is undecidable because it can be reduced from the Post Correspondence Problem (PCP), a well-established undecidable problem. The undecidability is rooted in the inherent limitations of deciding membership for non-regular languages despite their recognizability, highlighting principles from recursion theory. The complexity stems from CFG's expressive power and non-closure properties under certain operations, creating undecidable equivalence and language properties not solvable through algorithmic means .

The Omega(n log n) lower bound for comparison-based sorting signifies that any algorithm that sorts by comparing keys will require at least n log n comparisons in the worst case. This is proven using decision trees, where each internal node represents a comparison and leaves represent permutations of input elements. For sorting to be correct, each permutation must be uniquely reachable, necessitating at least n! leaves. The height of a binary decision tree with n! leaves is at least log(n!), which is approximated as Theta(n log n) using Stirling's approximation, establishing the lower bound .

Fixed-parameter tractability (FPT) signifies a classification for problems solvable in polynomial time related to specific parameters. An example is the k-Vertex Cover problem, where a branching algorithm systematically selects edges, ensuring either endpoint inclusion in the cover. Analysis gives a recursive time of T(k) = 2T(k-1), evaluated as O(2^k). Additional techniques like kernelization reduce instances to polynomial size relative to k, maintaining efficiency. FPT is crucial in practical settings, where certain dimensions or constraints bound problem size, allowing exact solutions within feasible runtimes .

Amortized analysis evaluates the average time taken per operation over a sequence of operations, smoothing out cost spikes. For dynamic array resizing by doubling, occasional expensive operations (array resizes costing O(n)) are infrequent compared to periodic cheap appends (O(1) each). Over n operations, total resizing costs up to O(n), averaging O(1) per operation. The accounting and aggregate methods confirm this stable cost distribution, proving that even with some costly steps, the append operation remains efficient on average under resizing by doubling .

Kosaraju's algorithm finds strongly connected components (SCCs) using two passes of depth-first search (DFS). The first pass records finish times in aggressive order; the second pass, on the transposed graph, processes vertices in decreasing finish time, ensuring leader discovery first. Correctness is assured because processing by finish time guarantees that all nodes in a component are reached from its root, effectively finding SCCs in O(V+E) time as connections are verified through backtracking .

Dijkstra's algorithm requires non-negative edge weights to ensure its greedy approach extends known shortest paths correctly without backtracking. Runtime is O((V+E) log V) using a binary heap, optimizing vertex extraction time through priority queues. With Fibonacci heaps, runtime reduces to O(V log V + E), enhancing efficiency in graph scenarios with high vertex degrees. The algorithm's correctness is guaranteed under non-negative conditions, as any intermediate vertex evaluations obey minimum path properties, ensuring shortest path computations upon extraction from the heap .

NP-completeness of a decision problem implies that it is as hard as the hardest problems in NP, meaning it is verifiable in polynomial time and every problem in NP can be reduced to it in polynomial time. For the Subset Sum problem, NP-completeness is established by showing it's in NP (with a subset as a certificate) and reducing known NP-complete problems like Partition to it. A reduction involves encoding subset sums with the target sum corresponding to a satisfying assignment, demonstrating that Subset Sum is both NP-hard and in NP .

The median-of-medians algorithm achieves linear-time complexity by partitioning the input into groups of five elements, finding the median of each group, and using the median of these medians as a pivot for partitioning. This ensures that at least 30% of elements are greater and less than the pivot, providing a consistent split. The recurrence relation T(n) = T(n/5) + T(7n/10) + O(n) resolves to T(n) = O(n), ensuring linear time. The pivot's property guarantees constant fraction partitions, maintaining correctness since it recursively solves the selection problem on smaller datasets .

Communication complexity arguments help establish lower bounds in the cell-probe model by demonstrating necessary information exchanges in hypothetical scenarios, quantifying essential interactions for certain data accesses. For static predecessor or membership problems, researchers like Pǎtraşcu use scenarios reducing these problems to communication tasks, where significant data must be exchanged to solve queries, proving that limited probes necessitate large data storage. Cells accessed represent direct computation units, and probe limits imply cost ceilings based on communication protocols and hard distributions, revealing inherent inefficiencies in space/time trade-offs .

The integrality of capacities in the max-flow min-cut theorem ensures that when capacities are integers, the maximum flow computed through algorithms like Ford-Fulkerson is also integral. Each augmenting path allows flows by full integral units, simplifying capacity constraints. Algorithmically, this characteristic supports determinism in path adjustments and termination. Using BFS as in the Edmonds-Karp algorithm, integrality allows iteration bounds to be established at O(VE), leveraging structured search patterns in the residual graph for efficient flow adjustments .