$n=1$ or any other constant does not matter.

Dark Mode

360 views

5 votes

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

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

6 votes

2

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$

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

5 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.**

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.

1

@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 l**arge as possible.**

Let me know if it makes sense.

0

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

2