Question

To determine the equivalence class \((f)\) of the function \(f(n) = {n^2}\) for the given relation \(R\).

Short answer

The equivalence class of \(f\) is given by

Step-by-step solution

Given data

Functions \(f\) and \(g\) are related by \(R\) if and only if \(f = \theta (g)\).

Concept  used of Equivalence class

An equivalence class is defined as a subset of the form\(\{ x \in X:xRa\} \), where\(a\)is an element of\(X\)and the notation "\(xR{y^{\prime \prime }}\)is used to mean that there is an equivalence relation between\(x\)and\(y\).

Find the equivalence class

By \(Ag(x) \le f(x) \le Bg(x)\forall x \ge k\),

\(g \in (f) \Leftrightarrow C{n^2} \le g(n) \le {D^2}\forall n \ge k\)(For suitable positive constants \(C,D\)and \(k\) ) So, the function \(g\) also has quadratic growth as \(f(n)\).

The equivalence class of \(f\) is given by

\((f) = \left\{ {g:{E^ + } - > {E^ + }:g(n) = A{n^2} + Bn + C\forall n > k,A > 0} \right\}\).