By expanding both log (n!) and n log n
log (n!) = log n + log (n-1) + ...... + log 2 + log 1 , n
terms here
n log n = log n + log n + ...... + log n + log n , and n
terms here
n log n *>* log (n!) , n > 1
n log n = log (n!) , n == 1
so as said in the mail above log (n!) = O( n log n )
Correct me if I am wrong.
K.V.Chandra Kumar
On 23/10/2007, Allysson Costa <[EMAIL PROTECTED]> wrote:
>
> When I'm talking about algorithm complexity can I afirm that:
>
>
> The complexity of LOG(N)! is NLOGN?
>
>
>
>
> Ajinkya Kale escreveu:
>
>
>
> On 10/22/07, Allysson Costa <[EMAIL PROTECTED]> wrote:
> >
> >
> > I have some doubts about summation notation
> > ============================================================
> > 1) Is there a formule like:
> >
> > SUM (LOG i) i=1 to i=n
> >
> > is equivalent to
> >
> > LOG (N)!
> >
> > This formule is true?
>
>
>
> Yes it is true .
>
>
> =============================================================
> > 2) What is relationship between LOG(N)! and NLOGN?
>
>
> nlog n = log(n^n) = log( n x n x n x .....n times)
>
> log(n!) = log( n x n-1 x n-2 x .......x 2 x 1)
>
> I dont think there is any relation between the 2. Atleast i am not aware
> of any till now.
>
> =============================================================
> > Thanks
> >
> > Allysson
> >
> >
> >
> >
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
