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.
