Prove that Thetan On2 notequalto On2Solution4 Ans Prove tha

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

Solution

4. Ans) Prove that (n) + O(n²) O(n²)

The two sets are, in fact, equal. You have already shown that (n)+O(n²)O(n²)

(n)+O(n²)O(n²).

To see why O(n²)(n)+O(n²), choose any f O(n²).

Then we know that there exist some constants C,n₀ such that for all nn₀, we have:

f(n)Cn²=(n)+(Cn²n)

It should be easy to see that n(n) and Cn²n O(n²).

Hence, we have f (n)+O(n²), as desired.