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

#1 brno792  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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)

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6064
  • View blog
  • Posts: 23,520
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 brno792  Icon User is offline

  • New D.I.C Head

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

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

Posted 11 September 2012 - 02:08 PM

View Postsepp2k, 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'?
Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • 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?
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1