is O(long n!)
n! is O(n^n) by sterling approximation
hence it is O(log n^n) = O(nlogn)
On Sun, Oct 28, 2012 at 11:14 PM, Pralay Biswas
<pralaybiswas2...@gmail.com>wrote:
> @ Siddharth :
> Well, here is how you may understand it:
> 1) There is an outer loop that runs n times. (k)
> 2) Then there is an inner loop where j is initially set to current k, but
> it halves itself in every iteration
> -- So for example, if k is 32, and j halves every time, then the
> inner loop runs for 5 times (32->16->8->4->2 etc)
> -- This is a log base 2 order depreciation in for all k
> 3) So for every k, the inner loop runs for log k times. k itself varies
> from 1 to n, hence O(nlogn)
>
> Hope this helps.
>
> #Pralay
> MS-CS, UC Irvine
>
> On Sun, Oct 28, 2012 at 10:38 AM, bharat b
> <bagana.bharatku...@gmail.com>wrote:
>
>> while loop : logj base 2 ..
>> ==> log1 + log2 + ... logn = log(n!) [since logab = loga + logb]
>> ==> O(log(n^n)) = O(nlogn)
>>
>>
>> On Sun, Oct 28, 2012 at 3:56 AM, Siddharth Malhotra <
>> codemalho...@gmail.com> wrote:
>>
>>> Can somebody explain how it is O(n log n).
>>> What is the significance of while loop in the above code?
>>>
>>> I understand that the for loop implies O(n),does the log n in the O(n
>>> log n) comes from the while loop?
>>> What if there where two while loops in the for loop separately?
>>>
>>> On Sat, Oct 27, 2012 at 3:26 AM, Pralay Biswas <
>>> pralaybiswas2...@gmail.com> wrote:
>>>
>>>> Yes!
>>>>
>>>>
>>>> On Fri, Oct 26, 2012 at 2:55 PM, rahul sharma
>>>> <rahul23111...@gmail.com>wrote:
>>>>
>>>>> for k=1 to n
>>>>> {
>>>>> j=k;
>>>>> while(j>0)
>>>>> j=j/2;
>>>>> }
>>>>> the complexity is big o is o(nlogn)
>>>>> am i ryt????
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
kriateive
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
