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

Page 1 of 1

## 4 Replies - 1599 Views - Last Post: 11 September 2012 - 02:31 PM

### #1 brno792

Reputation: 0
• Posts: 2
• Joined: 11-September 12

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

Posted 11 September 2012 - 01:36 PM

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.

Is This A Good Question/Topic? 0

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

• Saucy!

Reputation: 6192
• Posts: 23,919
• Joined: 23-August 08

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

Posted 11 September 2012 - 01:40 PM

Moved to Computer Science

### #3 sepp2k

• D.I.C Lover

Reputation: 2261
• Posts: 3,465
• Joined: 21-June 11

## 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.

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

### #4 brno792

Reputation: 0
• Posts: 2
• Joined: 11-September 12

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

Posted 11 September 2012 - 02:08 PM

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'?

### #5 mojo666

Reputation: 377
• Posts: 817
• Joined: 27-June 09

## 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?