Author |
Topic: Merge Arrays in constant space and linear time (Read 1982 times) |
|
hary
Junior Member
Posts: 107
|
 |
Merge Arrays in constant space and linear time
« on: Feb 6th, 2010, 1:10am » |
 Quote  Modify
|
Merge two sorted arrays one containing "m" elements and other caontaining "n" elements. We need to do this in constant space. Most of us know that linear time complexity for merging is possible. I am wondering if tconstant space complexity is possible. Can someone comment.
|
|
 IP Logged |
|
|
|
birbal
Full Member
Gender: 
Posts: 250
|
|
Re: Merge Arrays in constant space and linear time
« Reply #1 on: Feb 6th, 2010, 1:20am » |
Quote Modify
|
on Feb 6th, 2010, 1:10am, hary wrote:Merge two sorted arrays one containing "m" elements and other caontaining "n" elements. We need to do this in constant space. Most of us know that linear time complexity for merging is possible. I am wondering if tconstant space complexity is possible. Can someone comment.
|
|
I dont think constant space complexity is possible. But yes you can do it with min( m, n) extra space.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
newb
Newbie
Posts: 38
|
|
Re: Merge Arrays in constant space and linear time
« Reply #2 on: Feb 6th, 2010, 2:55am » |
Quote Modify
|
Quote:Merge two sorted arrays one containing "m" elements and other caontaining "n" elements. We need to do this in constant space. Most of us know that linear time complexity for merging is possible. I am wondering if tconstant space complexity is possible. Can someone comment.
|
|
where to store the merged arrays?
we must have space for that.
or do we have a single array of m+n size in which first m elemnts are sorted and last n elements are sorted?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Merge Arrays in constant space and linear time
« Reply #3 on: Feb 6th, 2010, 3:23am » |
Quote Modify
|
See here and here.
In summary, it's possible, but it's so complicated no one here has tried to post an algorithm for it 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: Merge Arrays in constant space and linear time
« Reply #4 on: Feb 8th, 2010, 7:17pm » |
Quote Modify
|
You can do merging in O(N), if the elements are maintained in a singly linked list.
Actually, you can do merge sort also using singly linked list in O(nlogn) without using any extra space.
|
| « Last Edit: Feb 8th, 2010, 7:18pm by bmudiam » |
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Merge Arrays in constant space and linear time
« Reply #5 on: Feb 9th, 2010, 3:26am » |
Quote Modify
|
on Feb 8th, 2010, 7:17pm, bmudiam wrote:| You can do merging in O(N), if the elements are maintained in a singly linked list. |
|
Yes, but we don't have a linked list, we have an array. That's what makes the problem problematic.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print