Asymptotic Notation

What is Asymptotic Notation?

It is method of analyze computer algorithms based on the input size. The most common method is O - Big O.

Define Big O Notation.

f(n) = O(g(n)) if there exists constants c and n₀ such that f(n) <= cg(n) for n>n₀

e.g. f(n) = 2n+6

c = 4, n₀ = 3 :g(n) = n because 2n+6 <= 4n. Thus f(n) = 2n + 6 = O(n)

What are other notations:

1. Big O - Upper bound : f(n) <= O(g(n))

2. Big Omega - Lower bound : f(n) >= O(g(n))

3. Big Theta -

4. Little Oh - Strict Upper Bound f(n) < O(g(n))

5. Little Omega - Strict Lower Bound f(n) > O(g(n))

Can you provide the classes of algorithms and the approximate relative value of n for them?