retagged by
1,025 views
4 votes
4 votes

Which of the following is true?

  1. $f(n)=O\left(\left(f\left(n\right)\right)^{2}\right)$
  2. $f(n)=O\left(g\left(n\right)\right)\Rightarrow 2^{f\left (n\right)}=O\left(2^{g\left(n\right)}\right)$
  3. $f(n)+O\left(f\left(n\right)\right)=\theta \left(f\left(n\right)\right)$
  4. Both (a) and (b)
retagged by

2 Answers

Best answer
5 votes
5 votes
Both $a$ and $b$ are false for decreasing functions like $\frac{1}{n}$.

Option C is always true.
selected by
2 votes
2 votes
Here Option A is Wrong Cz if fn is 1/n

f(n)==1/2=.5

f(n)^2 =.25

.25 < .5

Option B is Wrong CZ

 Take f(n)=2n & g(n)=n Which satisfies Antecedent part But not consequence part

Cz (2^2n=4^n )!=2^n

Now Why Option C is Correct.... [Answered By Will Win]

Let F(n) = n.

Let H(n) = O(F(n)).

That is, the order of growth of function H is asymptotically and inclusively upper bounded by the function F(n).

In simple words, H(n) <= F(n).

F(n) + O(F(n)) = Big Theta(F(n)) is correct as one can write is as

 'n + order of growth of a function less than and EQUAL to F(n) = Asymptotic growth of F(n)'.

Note: O(F(n)) will not be asymptomatically faster than F(n).

Because H(n) = O(F(n)) says it all.

While the asymptotic upper bound for F(n) isn't mentioned in option (c). And that was the tricky part.

Hence C is is the Correct Ans.
Answer:

Related questions

1 votes
1 votes
1 answer
1
Markzuck asked Jan 6, 2019
492 views
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
0 votes
0 votes
1 answer
2
Markzuck asked Dec 29, 2018
775 views
cant we write the recurrance relation for bar() as T(n) = 5T(n-1) + c,like cant we take both the recurrance call as combined as both have same parameter?and if not, then ...
2 votes
2 votes
0 answers
4
ashish pal asked Jan 22, 2018
651 views
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______A.) Ω(n)B.) θ(n2)C.) Ω(n2)D.) θ(n)How to do these type of questions ?