Design and Analysis of Algorithms20815 marksAsymptotic Notations
Write short notes on: a) Big Oh, Big Omega, Big theta b) Class P, Class NP and NP-Complete
Write short notes on: a) Big Oh, Big Omega, Big theta b) Class P, Class NP and NP-Complete [5]
--- Big Oh notation gives the asymptotic upper bound of a function. Definition: A function f(x) is said to be O(g(x)) if and only if there exist two positive constants c and x₀ such that: For all x = x₀ : f(x) <= c g(x) This means g(n) is the upper bound of f(n). The algorithm will never take mor...