Explain O, Ω &θ Notations with the help of Graph. And represent the following function using above notations.

(i) T(n) = 3n + 2

(ii) T(n) = 10n2 + 2n + 1

θ- Notation (Figure 3 (a)):

1. The theta notation bounds a function from above and below, so it defines exact asymptotic behavior.
2. A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants.
3. For example, consider the following expression. $3n^3 + 6n^2 + 6000 = θ(n^3)$
4. Formal definition: Let f and g be two functions defined on some subset of the real numbers then f(n) = θ (g(n)) as n→ infinity If there are exist positive constants ‘$n_o$’ and ‘$c_1$’ and ‘$c_2$’such that to the right of ‘$n_o$’, the value of f (n) always lies between $c_1g(n)$ and $c_2g(n)$ inclusive.

O- Notation (Figure 3 (b)):

1. The Big O notation defines an upper bound of an algorithm.
2. It bounds a function only from above.
3. For example, consider the case of Insertion Sort. It takes linear time in best case and quadratic time in worst case.
4. The time complexity of Insertion sort is $O (n^2)$. Note that $O(n^2)$ also covers linear time.
5. Formal definition: Let f and g be two functions defined on some subset of the real numbers then f(n) = O (g(n)) as n→ infinity If there are positive constants ‘no’ and ‘c’ such that to the right of ‘no’, the value of f (n)always lies on or below cg(n).

Ω-Notation (Figure 3 (c)):

1. The Omega notation defines a lower bound of an algorithm.
2. It bounds a function only from below.
3. For example, consider the case of Insertion Sort. The time complexity of Insertion sort is Ω (n).
4. But it is not very useful information about insertion sort, as we use worst case and sometimes in average case.
5. Formal definition: Let f and g be two functions defined on some subset of the real numbers then f(n) = Ω(g(n)) as n→ infinity If there are positive constants ‘$n_o$’ and ‘$c$’ such that to the right of ‘no’, the value of f (n)always lies on or above cg(n).