[brno792]

I know this is a math question. It is for algorithm time complexity analysis.

I need help writing a correct proof for this:

Prove that big-theta(n) + big-oh(n^2) != big-oh(n^2).


I know I need to find an instance where a constant c makes this statement false, but im not sure on the steps to get there.

Using the definitions:
theta(g(n)) = 0 <= c1g(n) <= f(n) <= c2g(n)
and
O((g(n)) = 0 <= f(n) <= c3g(n)

Thank you.

[JackOfAllTrades]

Moved to Computer Science

[sepp2k]

Unless I'm missing something, what you're trying to prove is not actually true.

Edit: I did miss something. Never mind me.

This post has been edited by sepp2k: 11 September 2012 - 02:08 PM

[brno792]

sepp2k, on 11 September 2012 - 02:03 PM, said:

Unless I'm missing something, what you're trying to prove is not actually true.

Im trying to prove that big-theta(n) + big-oh(n^2) is not equal to big-oh(n^2).

perhaps if I said 'is not an element of' instead of 'not equal to'?

[mojo666]

The main thing is that the left side of the equation has an extra constraint on the lower bound while the right side does not, so they can't be considered equivalent. I would think a proof by counter example would be sufficient. Let f(n)= log(n), does it satisfy both expressions?