1

Hello I've tried my best to understand big-theta and now I get the main conception of the proofs for Big-Oh and Big-Omega but i couldn't find and example that is close to my excercise, because i cant do the proof for that one:

Prove, by exhibiting witnesses, that 4n^2 + 4n = Big-Theta(2n^2 + 32n)

I know that i have to prove it for Big-Oh and Big-Omega in order to prove Big-Theta, but i have no idea how to start. I mean the equation on the right side confuses me.

blubb
  • 9,510
  • 3
  • 40
  • 82
Zee
  • 2,240
  • 4
  • 18
  • 18
  • 1
    BTW, theta is a set, so it is not proper to say 4n^2 + 4n = Big-Theta(2n^2 + 32n). Rather, say 4n^2 + 4n in Big-Theta(2n^2 + 32n). – ThomasMcLeod Mar 28 '11 at 21:11
  • 1
    @ThomasMcLeod, while what you said is true strictly speaking, I thought it was accepted convention to abuse notation like that. – Michael McGowan Mar 28 '11 at 21:53
  • Yes, this is the standard notation. Confusing at first but used in almost all algorithms books. – ypercubeᵀᴹ Mar 28 '11 at 22:36
  • 4
    I wouldn't say abusing, but `overloading the = operator`. – ypercubeᵀᴹ Mar 28 '11 at 22:39
  • Even if it is an abuse, it is a _very convenient_ abuse. –  Mar 29 '11 at 00:47
  • @ypercude, @Moron, it's not convenient if it's confusing. And using equality is confusing, because even if we used `=` as a theta equivalence operator, so that `4n^2 + 4n = 2n^2 + 32n`, it still makes no _mathematical_ sense that `4n^2 + 4n = theta(2n^2 + 32n)`. – ThomasMcLeod Mar 29 '11 at 02:04
  • 1
    @Thomas: It does make sense when it is explained. The confusing part is mainly (i think) because people think that `=` is commutative but when used with Θ and O notation it's not. For example, you can say `4n^2 + 4n = Θ(2n^2 + 32n)` but not `Θ(2n^2 + 32n) = 4n^2 + 4n` – ypercubeᵀᴹ Mar 29 '11 at 05:30
  • 2
    @THomas: Nope. It is very convenient in writing asymptotic expressions. For instance things like log n! = nlog n - n + O(log n). Sum_{primes p <= n} 1/p = log log n + A + O(1/log^2 n) etc. This is quite prevalent in mathematical literature and is really very convenient. Of course, unless you know what it means, you cannot make sense of those expressions... While I agree there might be some confusion to people who are unfamiliar, the convenience far outweighs the possible issues due to confusion. –  Mar 29 '11 at 05:50
  • @yper, @Moron, yes, `=` is used for that purpose in various texts. Maybe it's just me, but using `=` as a non-communitive operator offends my sense of symmetry (not to mention notational consistency). When I taught college CS, I asked students to use the $\in$ symbol to emphasize that Θ and O were sets. I found that that was pedologically helpful besides bring technically correct. – ThomasMcLeod Mar 29 '11 at 14:54
  • @Thomas - it's not just you. I think it's perverse to use `=` to indicate set membership, which is what is going on here. – Ted Hopp Mar 29 '11 at 21:28

1 Answers1

4

By the definition of big-theta, you need to show that there exist two constants, k1 and k2, such that for all sufficiently large values of n,

k1 * |2n^2 + 32n| <= |4n^2 + 4n| <= k2 * |2n^2 + 32n|

(Since your functions are all positive for positive n, you can drop the absolute values.) Just show that each inequality can be satisfied separately and you're done.

DaveTheMinion
  • 664
  • 3
  • 22
  • 45
Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • What is the equation that i would get. I'm sorry for the dumb question but I'm really unsure about the answer I get. – Zee Mar 29 '11 at 13:14
  • 1
    @Zee - let's take the left-hand inequality. As mentioned, we'll drop the absolute value signs. You need to show that there is a _k1_ and an _N_ such that for all _n_ > _N_, _k1_ * (2 _n_ ^2 + 32 _n_ ) <= 4 _n_ ^2 + 4 _n_ . This can be rewritten as (4-2 _k1_ )n^2 - 28 _n_ >= 0. For large _n_ , this will be dominated by the _n_ ^2 term, so it will eventually be positive provided 4 - 2 _k1_ is positive. So any _k1_ < 2 will do (such as _k1_ = 1). Once you pick a _k1_ , it's a simple exercise to calculate the threshold _N_ . A similar analysis can be used for the right side. – Ted Hopp Mar 29 '11 at 21:22