179 views

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).$

Subscribe to GO Classes for GATE CSE 2022

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).

True.

by
2 4

This is standard result.

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

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

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)

Answers for this question are options B,C,D

by
1 1

more precisely $n! < n^n$ which means strictly lesser.
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
I am talking about asymptotic analysis. it is always for $n \geq n_0$.

$n=1$ or any other constant does not matter.
ok sir i will edit the answer then
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$

1
2
3
121 views