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.

# Prove that theta(n) + O(n^2) != O(n^2)

Page 1 of 1## 4 Replies - 1703 Views - Last Post: 11 September 2012 - 02:31 PM

##
**Replies To:** Prove that theta(n) + O(n^2) != O(n^2)

### #2

## Re: Prove that theta(n) + O(n^2) != O(n^2)

Posted 11 September 2012 - 01:40 PM

Moved to Computer Science

### #3

## Re: Prove that theta(n) + O(n^2) != O(n^2)

Posted 11 September 2012 - 02:03 PM

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

Edit: I did miss something. Never mind me.

Edit: I did miss something. Never mind me.

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

### #4

## Re: Prove that theta(n) + O(n^2) != O(n^2)

Posted 11 September 2012 - 02:08 PM

### #5

## Re: Prove that theta(n) + O(n^2) != O(n^2)

Posted 11 September 2012 - 02:31 PM

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?

Page 1 of 1