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

Re: bigo theta
Quote:
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 .

Re: bigo 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 bigo of it. Then a subsequent question asked us to "Explain f(n) in simpler terms using theta" and I was like :?

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