First of all, this is my first post so... Hi. I've already tried using the search function, but couldn't find anything along the lines I was looking for. I'm trying to learn (more) about algorithm analysis - namely big-oh, big-omega and big-theta notation.

It's probably best that I post an example problem and go from there:

=======================================

Show that f(x) = x^2 + 2x + 1 is O(x^2)

The example proof states:

Clearly if x > 1 then x^2 > x > 1

So f(x) = x^2 + 2x + 1

<= x^2 + 2x^2 + x^2

= 4x^2

Using K = 1 and C = 4 as witnesses implies f(x) is O(x^2)

Alternate witnesses: K = 2, C = 3

=======================================

I'm missing more than a few points... How is this (simple) solution derived? In the example, it looks like the elements that aren't x^2 and raised to that and then added up... Is that because x^2 is the biggest term? What are witnesses, where are they used, and why are they given multiple possible values seemingly by magic?

I'm confused... Does this make sense to anyone?

Please help! Thanks in advance.