Question

Prove that Theta(n) +O (n^2) notequalto O(n^2)

Answer 1

Solution:| Consider an example for calculate the efficiency of function. To evaluate an expression of function findEfficiency (n) means findEfficiency function with parameter is size of the list input. Perform one comparison on each content in the list Then it will be the findE » ficiency (n) is equal to n . findEfficiency (n) /n will return 1 that can be expressed as findEfficiency (n)/n 1 That means the expression gives result as findEfficiency (n) grows no faster than n. From the big - O notation findEfficiency (n)O(n) Then calculate the comparison of inverse function is n/ findEfficiency (n)-1 It remains the results as bounded. From the function findEfficiency (n) it is grows faster than n. From above both the cases grows with same speed. That result in the form of findEfficiency(n) is ®n) In the case of findEfficiency (n) /n2 is also in the form of bounded. Then it will b h findE fciency (a) is equalt an That means the expression gives result as findEfficiency (n) grows no faster than n. From the big-O notation findEfficiency (n) = O(n2). . From the concept ofupper bound on the complexity of big - O notation is is O(n2), O(n3), O(n) and so on...

Then calculate the comparison of inverse function is nl findEfficiency (n)-n *From the above result n that is not bounded then it means findEfficiency (n) f0(n2 From the concept of lower bound and upper bound on the complexity of the findEfficiency function, the result will be +On2On2

Solution:

Consider an example for calculate the efficiency of function.

To evaluate an expression of function findEfficiency (n) means findEfficiency function with parameter is size of the list input.

• Perform one comparison on each content in the list
• Then it will be the findEfficiency (n) is equal to n .

findEfficiency (n) /n will return 1 that can be expressed as findEfficiency (n)/n = 1

That means the expression gives result as findEfficiency (n) grows no faster than n.

• From the big – O notation findEfficiency (n) = O(n).

Then calculate the comparison of inverse function is n/ findEfficiency (n) = 1

• It remains the results as bounded.
• From the function findEfficiency (n) it is grows faster than n.

From above both the cases grows with same speed.

That result in the form of findEfficiency(n) is Θ(n)

In the case of findEfficiency (n) /n² is also in the form of bounded.

• Then it will be the findEfficiency (n) is equal to n² .

That means the expression gives result as findEfficiency (n) grows no faster than n.

• From the big – O notation findEfficiency (n) = O(n²).

From the concept of upper bound on the complexity of big – O notation is is O(n²), O(n³), O(n⁴) and so on...

Then calculate the comparison of inverse function is n²/ findEfficiency (n) = n

• From the above result n that is not bounded then it means findEfficiency (n) ≠Θ(n²)

From the concept of lower bound and upper bound on the complexity of the findEfficiency function , the result will be Θ(n)+O(n²) ≠O(n²)