@ anand kindly elaborate a bit
On Mon, Jul 5, 2010 at 10:09 PM, Anand wrote:
> Use a Heap of n-way merging: O(klogn)
>
>
> On Sun, Jul 4, 2010 at 5:07 AM, Raajay wrote:
>
>> According to the problem there should be 'n * k' elements in all (on an
>> average). For merging all the elements into a
@divya complexity according to ur ques shud be O(klog n) (thats what i
think ... i may be wrong)
plzzz check 4m source where u take ques
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegro
Use a Heap of n-way merging: O(klogn)
On Sun, Jul 4, 2010 at 5:07 AM, Raajay wrote:
> According to the problem there should be 'n * k' elements in all (on an
> average). For merging all the elements into a single list one has to look at
> all the elements at least once. (For eg in case of mergin
According to the problem there should be 'n * k' elements in all (on an
average). For merging all the elements into a single list one has to look at
all the elements at least once. (For eg in case of merging two lists of size
n1 and n2, the worst case complexity in O(n1 + n2)).
Extending to the mu
sory its not not as i said ;(
On Sat, Jul 3, 2010 at 6:21 PM, jalaj jaiswal wrote:
> merge two lists at a time ... in O(k)
> thus reducing number of lists to half at every step
> i.e n*logk
> its more like bottom up merge sort .. look for it
>
>
> On Sat, Jul 3, 2010 at 11:06 AM, divya wrote:
1. First take two lists at a time and merge them so total elements parsed
for all lists =O(n)
This operation results in k/2 lists
2. Repeat steps till k/2 == 1.
*Time complexity of above solution = O(n logk)*
Step1 would loop through *logk *times and each operation would require
parsing all n elem
merge two lists at a time ... in O(k)
thus reducing number of lists to half at every step
i.e n*logk
its more like bottom up merge sort .. look for it
On Sat, Jul 3, 2010 at 11:06 AM, divya wrote:
> How do you merge n sorted lists with average length K in O(n*log(K))
> time?
>
> --
> You receiv
How do you merge n sorted lists with average length K in O(n*log(K))
time?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algoge
