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 bigtheta(n) + bigoh(n^2) != bigoh(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 14 Replies  1537 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
