recategorized by
802 views
7 votes
7 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).$
recategorized by

2 Answers

10 votes
10 votes

Answers for this question are options B,C,D

 

edited by
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
Answer:

Related questions

9 votes
9 votes
2 answers
3
GO Classes asked May 4, 2022
483 views
If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n)),$ then it is always true that$f(n) = o(g(n)).$$f(n) = \theta(g(n)).$$f(n) = \omega(g(n)).$both A and B are always true.