Theory of Computation20795 marksIntractability
Write short notes (Any two): a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy
Write short notes (Any two): a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy [5]
--- These are asymptotic notations used to describe the time or space complexity of algorithms as the input size n grows. --- Definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that: f(n) ≤ c · g(n) for all n ≥ n₀ - It gives the worst-case (upper bound) complexity. - Examp...