Bissoy.com
Doctors Medicines MCQs Q&A

Which one of the following statements is TRUE for all positive functions f(n) ?

Which one of the following statements is TRUE for all positive functions f(n) ? Correct Answer f(n<sup>2</sup>) = θ(f(n)<sup>2</sup>), when f(n) is a polynomial

The correct answer is option 1.

Concept:

Option 1: f(n2) = θ(f(n)2), when f(n) is a polynomial.

True, Theta is an Asymptotic Notation used to represent the asymptotically tight bound on the growth rate of an algorithm's runtime.

If f(n) = Θ(g(n)), then there exists positive constants c1, c2 such that 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n)

Explanation:

f(n2) = θ(f(n2)) here f(n) is polynomial

f(n) = n3

f(n2) = (n2)3 = n6

f(n2) = (n3)2 = n6all are equal.

Option 2: f(n2) = o(f(n)2)

False, The little o notation is one of them. Little o notation is used to describe an upper bound that cannot be tight.

If f(n) = o(g(n)), then there exists positive constants c such that 0 ≤ f(n) < c.g(n)

Explanation:

f(n2) = o(f(n)2) then there is no postive constants exists c
such that 0 ≤  f(n2) < 1.f(n)2)  

Option 3: f(n2) = O(f(n)2) when f(n) is an exponential function. 
 
False, Big-O notation represents the upper bound of the running time of an algorithm.
 
If f(n) = O(g(n)), then there exists positive constants c such that 0 ≤ f(n) ≤ c.g(n)
 
Explanation:
 
If f(n) = O(g(n)), then there no positive constants exists c 
such that 0 ≤ f(n2) ≤ c.f(n2)
 
Option 4: f(n2) = Ω(f(n)2)
 
False, Omega notation represents the lower bound of the running time of an algorithm.
 
If f(n) = Ω(g(n)), then there exists positive constants c such that 0 ≤ c.g(n) ≤ f(n)
 
Explanation:
 
If f(n) = Ω(g(n)), then there no positive constants exists  c
such that 0 ≤ c.f(n2)  ≤ f(n2) 
 

Hence the correct answer is f(n2) = θ(f(n)2), when f(n) is a polynomial.

Related Questions

As per the RBI Act, 1934, the following functions are described as the functions of a Central Bank:
1. Banking functions
2. Advisory functions
3. Supervisory functions
4. Promotional functions
Identify the correct combination:
In the question below, some statements are given followed by some conclusions. Taking the given statements to be true even if they seem to be at variance from commonly known facts, read all the conclusions and then decide which of the given conclusions logically follows the given statements. Statements: I. All Eagle are Lizard. II. All rabbit are snake. III. All snake are Eagle. Conclusions: I. All Rabbit are Lizards. II. All Eagle are Rabbit. III. All Lizard are Snake. IV. All Snake are Lizard. 
Three statements are given, followed by four conclusions numbered I, II, III and IV. Assuming the statements to be true, even if they seem to be at variance with commonly known facts, decide which of the conclusions logically follow(s) from the statements. Statements: All books are pens. All pens are erasers. All erasers are files. Conclusions: I. All pens are files. II. All pens are books. III. All files are books. IV. All files are pens.
Read the given statements and conclusions carefully. Assuming that the information given in the statements is true, even if it appears to be at variance with commonly known facts, decide which of the given conclusions logically follow(s) from the statements. Statements: i. All lipsticks are makeup. ii. All makeups are beauty products. iii. All beauty products are skincare. Conclusion: A. All makeups are skincare. B. All beauty products are lipsticks. C. All lipsticks are skin care. D. All skincare are makeup. 
Read the given statements and conclusions carefully. Assuming that the information given in the statements is true, even if it appears to be at variance with commonly known facts, decide which of the given conclusions logically follow(s) from the statements. Statements: All Books are Pens. All Pens are Erasers. All Erasers are Files. Conclusions: I. All Pens are Files. II. All Pens are Books. III. All Files are Books. IV. All Files are Pens.
Read the given statements and conclusions carefully. Assuming that the information given in the statements is true, even if it appears to be at variance with commonly known facts, decide which of the given conclusions logically follow from the statements. Statements: 1. All parakeets are cuckoos. 2. All cuckoos are rabbits. 3. All rabbits are snakes. Conclusions: I. All parakeets are snakes. II. All snakes are cuckoos. III. All rabbits are parakeets. IV. All cuckoos are snakes.
Read the given statements and conclusions carefully. Assuming that the information given in the statements is true, even if it appears to be at variance with commonly known facts, decide which of the given conclusions logically follow(s) from the statements. Statements: A. All purses are coins. B. All coins are rupees. C. All rupees are pink. Conclusions: I. All purses are pink. II. All pink are coins. III. All rupees are purses. IV. All coins are pink.
Read the given statements and conclusions carefully. Assuming that the information given in the statements is true, even if it appears to be at variance with commonly known facts, decide which of the given conclusions logically follow from the statements Statements: All ducks are tigers. All tigers are monkeys. All monkeys are cows. Conclusions: I. All tigers are cows. II. All monkeys are ducks. III. All ducks are cows. IV. All cows are tigers.
Consider the following statements in respect of relations and functions: 1. All relations are functions but all functions are not relations. 2. A relation from A to B is a subset of Cartesian product A × B. 3. A relation in A is a subset of Cartesian product A × A. Which of the above statements are correct?
In the following question below are given some statements followed by some conclusions based on those statements. Taking the given statements to be true even if they seem to be at variance from commonly known facts. Read all the conclusions and then decide which of the given conclusion logically follows the given statements. Statements: I. All cat are beautiful. II. No peacock is cat. Conclusions: I. All beautiful are cat. II. All peacock are beautiful. III. All cat are peacock.