edited by
9,446 views
9 votes
9 votes

Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^{2}.$ Which of the following statements is/are $\text{TRUE}?$

  1. $f \in O(g)$
  2. $f \in \Omega(g)$
  3. $f \in o(g)$
  4. $f \in \Theta(g)$
edited by

4 Answers

9 votes
9 votes

 

Detailed Description about “$\in $” and  “$=$”  notations is given in this video  https://youtu.be/i16AdymW7Y4

\line(1,0){250}

 

Some students might be confused by the “$\in$” symbol in the options, instead of “$=$”.

Let me tell you that writing $f \in O(g)$ is a better (technically correct) way than writing $f = O(g).$

If the options had “$=$” instead of “$\in $”, the answer wouldn’t change. 

We write $f (n) = O (g (n))$ to indicate that a function $f (n)$ is a member of the set $O (g (n))$ and vice versa.

$O(f(n))$ is a set. So, writing $f \in O(g)$ is a better (technically correct) way than writing $f = O(g).$

To keep it simple, you can think of $f = O(g)$ as same as $f \in O(g).$

Reference: Introduction to Algorithms by CLRS(Cormen):


Basically, for $g(n) = n^2$, $O(g)$ is a Set of functions which grow slowly (or same) as compared to $g$ as input $n$ grows larger.

Hence, $O(n^2) = \{ n, n^2, logn, 1, constant, nlogn, n^{1.9} , \dots \}$

Keep It Simple: $f \in O(g)$ is same as $f = O(g)$.

edited by
5 votes
5 votes

The answer of this question depends on the assumption and without making assumption, we can’t say which option is correct here. 

Answer is given at the end, so you can skip the details if you want.

There is a misconception that $\mathcal{O}$-notation is for sufficiently large values of variable $n.$ In CLRS, there is very little information is given about Asymptotics and some people can think that it is always for sufficiently large values of $n$ which is half truth about Asymptotics. One more misconception people can take from CLRS that believing $\log^2 x = (\log x)^2$ but again this is not completely true. Both $\log^2 x = (\log x)^2$ and $\log^2 x = \log (\log x)$ are correct.

Asymptotics is not part of only Algorithms, it is used in Analytic Number Theory and some other branches of mathematics. This topic can be found in discrete mathematics text also and so it is also part of "functions” topic which is mentioned in gate cse syllabus and also there is no harm to know about the complete truth of something and even in CLRS, limiting behavior of $n \rightarrow 0$ is mentioned while writing $e^n = 1+n + \Theta(n^2).$


It should be mentioned in the question that what is the limiting value of $n.$ Also, whether set of natural number starts with zero or one or they have to define the set of natural numbers.


The answer here is long but you probably learn many things here. This answer covers some basics of Asymptotics which might not be present here and mostly it is taken from a book "Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik". It is recommended to read this book once in a lifetime if you have interest in mathematics or have taken the Discrete Mathematics course. Also, mentioning that Knuth is a ACM Turing Award winner and like Discrete Mathematics book, his “The Art of Computer Programming” book is also famous.

Some points can be noted as:      

1. The variables used with $\mathcal{O}$ notation are generally subject to side conditions. If we have a function in $n$ as $f(n)= \frac{1}{3}n^3 + \frac{1}{2}n^2 + n$ where $n$ is a real number then we can't write $f(n)= \mathcal{O}(n^3)$ when $n \rightarrow 0$ and similarly we can't write $f(n)= \mathcal{O}(n)$ when $n \rightarrow \infty.$ So, we can't use the $\mathcal{O}$-notation if the side condition is not given but if it is given that $|n| \geq 1$ then we can write $f(n)=\mathcal{O}(n^3)$ and if it is given that $|n| \leq 1$ then we can write $f(n)=\mathcal{O}(n).$     

 

2. There can be infinitely many definitions of $\mathcal{O}$-notation depends on the limiting condition. It is not necessary that $n \rightarrow 0$ or $n \rightarrow \infty.$ Limiting condition can be $n \rightarrow 1$ or $n \rightarrow 2$ and so on.    

 

3. We might say $$f(n) = \mathcal{O}(g(n)) \; \; as \;\; n \rightarrow \infty$$   which means limiting condition holds "near" $\infty$ and "near" means that there exists two constants $C$ and $n_0$ such that 


$$|f(n)| \leq C|g(n)| \; \; \;\; whenever\;\; n \geq n_0$$


Here, value of $C$ and $n_0$ might be different for each $\mathcal{O}$ but they do not depend on $n.$  $\mathcal{O}(g(n))$ is used as an incompletely specified function.  


Similarly, we write


 $$f(n) = \mathcal{O}(g(n)) \; \; as \;\; n \rightarrow 0$$   
 which means there exist two constants $C$ and $n_0$ such that $$|f(n)| \leq C|g(n)| \; \; \;\; whenever\;\; n \leq n_0$$


 Similarly we can write $$\ln n = (n-1) + \mathcal{O}((n-1)^2)\;\; as\;\; n \rightarrow 1$$ 


 4. We can write $$\frac{1}{3}n^3 + \frac{1}{2}n^2 + n=\mathcal{O}(n^3)\;\; as\;\; n \rightarrow \infty$$
 But we should never write this equality reversely. $\mathcal{O}(g(n))$ represents the set of all functions $f(n)$ such that $|f(n)| \leq C|g(n)|$ for some constant $C$ with some limiting condition. If $S_1$ and $S_2$ are two sets of functions then $S_1 + S_2$ represents the set of all functions of the form $f(n) + g(n)$ where $f(n) \in S_1$ and $g(n) \in S_2$ and similarly we can use notations like $S_1-S_2, S_1S_2,S_1/S_2,\sqrt{S_1},e^{S_1}, \ln S_1$ etc.


 5. An "equation" between the set of functions is a $\textit{set inclusion}$ and then "=" in equation means $\subseteq.$ So, "=" does not only means $\in,$ it can be $\subseteq$ when we have a set of functions on both sides of "=" in an equation.


For example the in "equation" $n^2 + \mathcal{O}(n) = \mathcal{O}(n^2),$ "=" is used for set inclusion $\subseteq.$ Here, it is like $S_1 \subseteq S_2$ where $S_1$ is a set of functions of the form $n^2 + f(n)$ such that there exists a constant $C_1$ with $|f(n)| \leq C_1 |n|$ and $S_2$ is a set of functions $g(n)$ such that there exists a constant $C_2$ with $|g(n)| \leq C_2 |n^2|$ with some limiting condition on $n.$


6. If there are several variables while using $\mathcal{O}$ notation then this $\mathcal{O}$ notation represents the set of functions of two or more variables, not just one and the domain of each function is every variable that is currently "free" to vary.  


For example,  

$$\sum_{k=0}^{n} (k^2 +\mathcal{O}(k)) = \frac{1}{3}n^3 +\mathcal{O}(n^2),\;\;\; integer\;\; n\geq0$$


The expression $k^2 + \mathcal{O}(k)$ on the left side stands for the set of all two-variable functions of the form $k^2 + f(k,n)$ such that there exists a constant $C$ with $f(k,n) \leq Ck$ for all $0 \leq k \leq n.$


Hence,


$$\sum_{k=0}^{n} (k^2 +f(k,n)) =\sum_{k=0}^{n} k^2 + \sum_{k=0}^{n}f(k,n) = \frac{1}{3}n^3 + \frac{1}{2}n^2+\frac{1}{6}n + f(0,n)+f(1,n)+f(2,n)+...+f(n,n)$$


Now,


$|\frac{1}{2}n^2 + \frac{1}{6}n +f(0,n)+f(1,n)+...+f(n,n)|$


$\leq \frac{1}{2}n^2 + \frac{1}{6}n^2 + C.0 + C.1 + ...+C.n$


$< n^2 + C(n^2+n)/2$


$< (C+1)n^2$


So, above equation is correct.


7. Big Omega is defined with lower bounds as:


$$f(n) = \Omega (g(n)) \Leftrightarrow g(n) = O(f(n))$$

And, Big Theta is defined for exact order of growth as:


$$f(n) = \Theta(g(n)) \Leftrightarrow f(n) =O(g(n))\;\; and \;\; f(n)=\Omega(g(n))$$  


And, Edmund Landau invented a "little oh" notation as:


$f(n) = o(g(n)) \Leftrightarrow f(n) \prec g(n) \Leftrightarrow \lim_{n\to a} \frac{f(n)}{g(n)}=0$


($\prec$ is used for "asymptotic growth ratios")



Now Comes to the given question,


$f(n)=n$ and $g(n) = n^2$ and assuming the set of natural numbers starts with $0.$


For $|n|\geq 1,$ $f(n) \in \mathcal{O}(g(n))$ and so, $g(n) \in \Omega(f(n))$  but for $|n|\leq 1,$ it is also true that $g(n) \in \mathcal{O}(f(n))$ and so, $f(n) \in \Omega(g(n)).$ 


Since for $|n| \geq 1,$ $f(n)$ and $g(n)$ don't have the same order of growth and so, $f \notin \Theta(g).$ 


Since $f(n)$ and $g(n)$ are sequences and so according to the definition, we have to find the limit of a sequence and assuming limiting condition as $n \rightarrow \infty$ then we need to find $\lim_{n\to\infty} \frac{f(n)}{g(n)}.$ If it is zero then we can say $f \in o(g).$


So here, for $n \rightarrow \infty$, $\lim_{n\to\infty}\frac{n}{n^2} = \lim_{n\to\infty}\frac{1}{n}=0$ because sequence converges to zero when $n \rightarrow \infty$ and so $f \in o(g)$ but if we assume $n \rightarrow 0$ then we can't write $f \in o(g)$ because then the ratio of two sequences $\{f(n)\}$ and $\{g(n)\}$ would be unbounded.

edited by
0 votes
0 votes

ABUSE OF NOTATION.  O(g(n)) indicates a set. Writing “belongs to” in place of “equal to” won’t change the answer, rather the former is better way of notation.

Answer:

Related questions

21 votes
21 votes
4 answers
1
admin asked Feb 15, 2023
11,270 views
Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ expressed in pseudocode as follows:Function_1 | Function_2 while n 1 do | for i = 1 to 100 * n do for ...
8 votes
8 votes
1 answer
2
12 votes
12 votes
3 answers
3
admin asked Feb 15, 2023
11,102 views
Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?Function Callmalloc CallPage FaultSystem Call