GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 14
in Programming recategorized by
179 views
4 votes
4 votes

Which of the following(s) is/are true?

  1. If $f(n) = O(n^2)$ then $f(n) = O(n).$
  2. If $f(n)$ is $O(3^{\log_{10}n}),$ then $f(n)$ is $O(n^2).$
  3. The function $f(n) = \lg(n!) = O(n \lg n).$
  4. Growth of the sum $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ can be described by $\theta(\log n).$
in Programming recategorized by
by
2 102 24
179 views

Subscribe to GO Classes for GATE CSE 2022

2 Answers

4 votes
4 votes

Answer :- B, C, D.


Option A : If f(n) = O(n^2) then f(n) = O(n).

False. Counter example, when f(n) = n^2.


Option B : If f(n) = O(3 $^{log_{10}n}$) then f(n) = O(n^2).

Here, Put $log_{10}n$ = k $\implies$ n = 10 $^{k}$.

then 3 $^{log_{10}n}$ becomes 3 $^{k}$ and n $^{2}$ becomes  10 $^{2k}$.

We know 3 $^{k}$ <= 10 $^{2k}$.

Therefore, 3 $^{log_{10}n}$ = O(n $^{2}$). 

By transitivity, f(n) = O(n$^{2}$).

True.


Option C : log (n!) = O(nlogn).

True. This is standard result.


Option D : Growth of the sum 1 + ½ + 1/3 + ⋯ + 1/n can be described by θ(logn).

We know 1 + ½ + 1/3 + ⋯ + 1/n = log n + $\gamma$ = θ(logn). 

(For more information, refer to the links given in following comments)

True.


 

edited by
by
2 4

3 Comments

This is standard result.

If you can add an explanation or link to already explained article then this could be the best answer.

Also mention in option D that is also the harmonic series.

0
0
About the thing written as standard result

bro in the class sir had explained in detail that asymptotically

Log(n!) is exactly equal to log(n^n)

so we can write log(n!) = theta(nlog(n))

Since we are able to write in theta we can also write the same thing in big oh

Also no one other than go classes students can access these tests so it would be easy for them to remember when they see the relation between the two functions as they would have already watched the lecture

so there won't be an issue with this i guess
1
1

The above line ,

“We know $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+....+\frac{1}{n}=\log n$ “ is wrong . 

The sum is not actually equal to logn , it is $\Theta (\log n)$.

Proof is here. 

https://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series

There is actually no close form formula for the harmonic sum , 

one of the approximation of the harmonic sum is

$(\log n)+\gamma$ where $\gamma =0.577$ ,Mascheroni constant .There are some other more accurate approximations there as well.

https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

1
1
4 votes
4 votes

Answers for this question are options B,C,D

 

edited by
by
1 1

5 Comments

more precisely $n! < n^n$ which means strictly lesser.
1
1
Sir i also thought of that initially but what stopped me is that

when n = 1

n! and n^n both are 1 so in this case n! = n^n

so i wrote n! <= n^n
0
0
I am talking about asymptotic analysis. it is always for $n \geq n_0 $.

$n=1$ or any other constant does not matter.
2
2
ok sir i will edit the answer then
0
0
To be more precise, asymptotic analysis is not always for $n \geq n_0.$

Asymptotic analysis or asymptotic mean any approximate value that gets closer and closer to the truth when some parameter approaches a limiting value.

So, depends on $n$ whether it approaches to infinity or zero, we take $n \geq n_0$ or $|n| \leq n_0$

We might say,  $ f(n) = O(g(n))$ as $n \rightarrow 0$ which means that there exist constants $C$ and $n_0,$

such that $|f(n)| \leq C|g(n)|\;\;$ whenever $|n| \leq n_0$
0
0
Answer:

Related questions