Use the formal definitions of BigOh BigOmega and BigTheta to

Use the formal definitions of Big-Oh, Big-Omega, and Big-Theta to prove the following. 1. (n + l)^x = O(n^x) for all x greaterthanorequalto 1. 2. If f(n) = phi(n) and = phi(n^2), then f(n) + g(n) = phi (n^2).

Solution

O(constant) is constant time hence it will not be considered while calculating the complexity

O(n+1)^x=O(n^x+1^x)

=O(n^x)

Here the complexity with higher power is considered and it is the complexity of the equation hence theta(n^2)