Question

1- Show that (n^3+3n^2+3n+1) / (n+1) is O (n2 ). Use the definition and proof of big-O notation.

2- Prove using the definition of Omega notation that either 8 n is Ω (5 n ) or not.

please help be with both

Answer 1

1) The first equation can be easily evaluated to simplified form :

Now,

If  , then

Which means for all values of n, the upper range of the given function would have an upper bound of 4n^2.

So, the complexity of the function in Big - Oh Notation would be O(n^2).

2)  Omega Notation, Ω

The notation is the best way to represent the lower bound of any algorithms running time in terms of the input. It gives an estimate of best time complexity of the function.

For all values of n i.e. , the relation holds true. Hence, the function g(n) = 5^n gives a lower bound to the function f(n) = 8^n for all .
Hence f(n) can be represented in omega notation as .

Please upvote the answer if it helps you.