# Math Help - big-o theta

1. ## big-o theta

I am working on a problem where I must prove that

n log n + n + log n 2 is in theta (n log n)

part of proving this is proving that

nlogn+n+logn <=M(nlogn)

I am just completely confused on how to prove this. An example from the notes which is much simpler looks like this

example:
 f (n) = 2n2 + 4 and
 g(n) = n2
Show f (n) ∈ Θ(g(n))
proof:
1. let M1 = 2
2. let M2 = 4
3. let n0 = 2
4. choose any n > n0
5. ⇒ n > 2
6. ⇒ n2 > 4
7. ⇒ n2 > 2
8. ⇒ 2 < n2
9. ⇒ 4 < 2n2
10. ⇒ 2n2 + 4 < 4n2
11. ⇒ 2n2 ≤ 2n2 + 4 ≤ 4n2
12. ⇒ M1n2 ≤ 2n2 + 4 ≤ M2n2
13. ⇒ M1g(n) ≤ f (n) ≤ M2g(n)
∴ f (n) ∈ Θ(g(n)) 

I am just so confused because nowhere can I find any rules or steps to finding M1 and K.

2. ## Re: big-o theta

nlogn+n+logn <=M(nlogn)
Clearly, n log(n) is the dominant term here. If we could prove that n <= n log(n) and log(n) <= n log(n) for all n starting from some n0, then n log(n) + n + log(n) <= 3n log(n) for all n > n0. Note that log(n) >= 1 when n >= 2 (if logarithm is to the base 2).

Hint: In plain text, it is customary to denote exponentiation using ^. For example, n^2 denotes $n^2$.

3. ## Re: big-o theta

Thanks you very much for your reply!

Just a quick related question, not sure if anyone has an answer.

Today on an in class quiz they gave us an algorithm and had us find the big-o of it. Then a subsequent question asked us to "Explain f(n) in simpler terms using theta" and I was like :?

4. ## Re: big-o theta

I am not sure, perhaps there is a function simpler than f(n) that is still Theta with f(n).