1. ## Theta notation

Hi peoples,

I have a problem with theta notations and was wondering if anyone could give me a hand?

The question is:

4nlgn + n + 6

Where I have to select the theta notation and justify my answer.

Many thanks.

Hi peoples,

I have a problem with theta notations and was wondering if anyone could give me a hand?

The question is:

4nlgn + n + 6

Where I have to select the theta notation and justify my answer.

Many thanks.
$f(n) \in \Theta(g(n)) \textbf{ iff }\exists (C,C'>0), n_0 : \forall (n>n_0) \; |Cg(n)| < |f(n)| < |C'g(n)|$

I claim $4n\log n + n + 6 \in \Theta(n\log n)$, can you find C and C', such that the definition holds?

3. Thanks Isomorphism,

But unfortunately, what you wrote has meant nothing to me. I can't figure out what you have written. Would you mind if you 'dumb' it down for me please?

Thanks

4. I'm not really getting your question.. are you talkin about functions growth here.. ?? Omega and big-O and these kind of things..?

5. Originally Posted by MMM88
I'm not really getting your question.. are you talkin about functions growth here.. ?? Omega and big-O and these kind of things..?
Yes I think he means that...

Thanks Isomorphism,

But unfortunately, what you wrote has meant nothing to me. I can't figure out what you have written. Would you mind if you 'dumb' it down for me please?

Thanks

Hmm what is your definition of Theta function?

In simple words, I am saying that 4nlgn+n+6 has the same growth rate as nlogn.

6. Alright, in order to show that a specific funtion is (theta) some other function, we have to check the big-O and Omega notations first.

In other words..

If we have f(n) = n - 27 as our function and we need to show whether f(n) is theta (log n) for instance. Then first we have to show that f(n) is omega (log n) and f(n) is big-o (log n) at the same time. If those two derivations apply to the fucntion then we can say that f(n) IS theta (log n).
If one of them fails then f(n) is not theta (log n).
I'm not sure if it makes sense to you here or even if this what you mean by your question. The question is not clear.. whats the fucntion that were supposed to be basing our first fucntion(the one you mentioned) on ??

7. Originally Posted by MMM88
Alright, in order to show that a specific funtion is (theta) some other function, we have to check the big-O and Omega notations first.

In other words..

If we have f(n) = n - 27 as our function and we need to show whether f(n) is theta (log n) for instance. Then first we have to show that f(n) is omega (log n) and f(n) is big-o (log n) at the same time. If those two derivations apply to the fucntion then we can say that f(n) IS theta (log n).
If one of them fails then f(n) is not theta (log n).
I'm not sure if it makes sense to you here or even if this what you mean by your question. The question is not clear.. whats the fucntion that were supposed to be basing our first fucntion(the one you mentioned) on ??
Hmm I am quite confused. Are you telling me or the original poster?

Because I am pretty sure the answer is nlogn

8. Originally Posted by Isomorphism
Hmm I am quite confused. Are you telling me or the original poster?

Because I am pretty sure the answer is nlogn
No, I was actually talking to the one who made the thread.