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

Answers for this question are options B,C,D

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$

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.

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)

@shishir__roy bro, you should write 1 more condition in the explanation of option B : (K is large).

because for a small value of k we just can’t say anything about the comparison.

If f(n) = O(3^log10n) then f(n) = O(n^2).

if you are taking some value of n (10^k) you should take it as large as possible.

Let me know if it makes sense.

@Udhay_Brahmi we're not taking some value of $n$, we're saying put $\log_{10}{n} = k$ to change (simplify) function variable from $n$ to $k$.