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