Its nlogn dude On Wed, Oct 31, 2012 at 8:03 PM, jai gupta <[email protected]> wrote:
> 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 < > [email protected]> 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 >> <[email protected]>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 < >>> [email protected]> 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 < >>>> [email protected]> wrote: >>>> >>>>> Yes! >>>>> >>>>> >>>>> On Fri, Oct 26, 2012 at 2:55 PM, rahul sharma <[email protected] >>>>> > 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 [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?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 [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?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 [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?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 [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?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 [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?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 [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?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 [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?hl=en.
