in Programming recategorized by
360 views
5 votes
5 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
360 views

2 Answers

6 votes
6 votes

Answers for this question are options B,C,D

 

edited by

4 Comments

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


 

edited by

4 Comments

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

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

0
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
2
Answer:

Related questions