# Theta notation

• May 20th 2008, 04:35 AM
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.
• May 20th 2008, 05:16 AM
Isomorphism
Quote:

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.

$\displaystyle 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 $\displaystyle 4n\log n + n + 6 \in \Theta(n\log n)$, can you find C and C', such that the definition holds?
• May 21st 2008, 05:21 AM
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
• May 22nd 2008, 12:05 AM
MMM88
I'm not really getting your question.. are you talkin about functions growth here.. ?? Omega and big-O and these kind of things..?
• May 22nd 2008, 01:15 AM
Isomorphism
Quote:

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

Quote:

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.
• May 22nd 2008, 01:31 AM
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 ??
• May 22nd 2008, 02:00 AM
Isomorphism
Quote:

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(Worried). Are you telling me or the original poster?

Because I am pretty sure the answer is nlogn
• May 22nd 2008, 02:46 AM
MMM88
Quote:

Originally Posted by Isomorphism
Hmm I am quite confused(Worried). 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.