Why is n^2 + 2n + 2 equal to O(n^2)?

When talking about asymptotic notation you usually use really big values of n and you try to find by what mathematical function is your program bounded.

In this case, you have 2 functions n^2 and 2n (let's ignore the constant for now).

If you plot the graphs of these you can see the following:

Although 2n is slightly higher than n^2 at the beginning, once n goes to infinity, 2n will always be lower than n^2

So if your method has a complexity of O(n^2 + 2n), it doesn't really matter that much (or it's negligible) when n goes to infinity the value of 2n, because your program will always be bound by n^2. You can apply the same reasoning to why a constant doesn't matter that much, even if it's a huge one.

Also, in asymptotic notation, you often do this "simplification" when you have sums, which is the case. However, this would be different if the complexity was O(n^2 * 2n), which if I'm not mistaken would end up being O(n^3) - constants don't matter, so we can get rid of the 2 and then you have n^2 * n.

An algorithm's running time (time complexity) is usually expressed as a function of the size of the input.

f(n) = n² + 2n + 2 where n is the size of the input

The Big-O notation is now used to express the asymptotic behavior of the complexity (the function) when the input size or n increases drastically. (This is of interest because the running time for small inputs is usually inconsequential).

Simply put, by looking at the function's terms and assuming n to be very large

• n² is a quadratic growth
• 2n grows with a small constant factor, and is a linear growth
• 2 is a constant and is therefore negligible

it becomes apparent that the n² term dominates and contributes the most to the time complexity, thus O(n²).