What is Asymptotic notation ? Define Big O notation.

Concept

Asymptotic notation describes how a function grows as the input size n tends to infinity. It ignores constant factors and lower-order terms so algorithmic resource growth can be compared independently of machine details.

Big O, Big Omega, and Big Theta express asymptotic upper, lower, and tight bounds, respectively.

Application

For eventually nonnegative functions f and g, f(n) ∈ O(g(n)) if there exist constants c > 0 and n0 ≥ 0 such that 0 ≤ f(n) ≤ c g(n) for every n ≥ n0. Thus, g(n) is an asymptotic upper bound for f(n) within a constant factor.

1. For f(n) = 3n + 2, choose c = 4 and n0 = 2.

2. For every n ≥ 2, 3n + 2 ≤ 4n; therefore f(n) ∈ O(n).

Cross-check and contrast

At n = 2, both sides equal 8. For larger n, the difference 4n − (3n + 2) = n − 2 remains nonnegative, so the inequality continues to hold.

Therefore O(n) is a valid asymptotic upper bound. The same function is also O(n2), but Θ(n) gives its tight growth rate.