Question

Formally prove that n^2 + n + 1 is in O(n^2).
Solution:
Let T(n) = n^2 + n + 1. Let f(n) = n^2.
Choose c = 3, and N = 1. Then, we know T(n) is in O(n^2) if we can prove
T(n) <= c f(n),
or equivalently, n^2 + n + 1 <= 3 n^2, for all n >= 1.
Is this inequality true? Well, for any n >= 1, we know that 1 <= n <= n^2.
Hence, all of the following are true:
1 <= n^2
n <= n^2
n^2 = n^2
Adding the left and right sides of these inequalities together, we have
n^2 + n + 1 <= 3 n^2, which completes the proof.

Answer 1

Answer:

See proof below

Explanation:

The Question has already been answered (along with the question you submitted).

I guess you need an explanation.

To start with;

Formally prove that n² + n + 1 is in O(n²)

This means that we are to prove that for all values of n≥k, there's a constant c.

The constant c is in such a way that

n² + n + 1 ≤ c * n²

To complete this, our task is in two folds

1. To assign any value to k

2. To solve for the value of c

The easiest value to work with is k = 1

So, n ≥ k becomes

n ≥ 1

At this point, we're done with step 1.

The step 2 is to show that for some constant c, the right hand side will always overtake the left hand side.

Already we have that

n ≥ 1 ----- multiply both sides by n

n² ≥ n

....

If we continue the sequence,

Keeping in mind that the coefficient of n must be equal to the term in check.

We'll have

n² ≥ n ≥ 1 ----- for n² (coefficient is 1)

Moving to the n, next to n² (coefficient is 1)

We'll have

n² ≥ n ≥ 1

Then, we'll move to +1, next to n (coefficient is 1)

We'll have

n² ≥ n ≥ 1

And so on...

Limiting the constraints to the first three

By adding the n²'s together

We have;

n² + n + 1 ≤ n² + n² + n²

n² + n + 1 ≤ 3n²

So, c = 3 and n ≥ 1

Hence, we've shown that n² + n + 1 is a function of O(n²)

.....

To check

Let n = 3

3² + 3 + 1 ≤ 3(3)²

9 + 3 + 1 ≤ 27

13 ≤ 27

This will be valid for all values of n ≥ 1