Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote -2 down vote favorite
1

I don't know what is the relation between m and n? I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. So, how to I know if n/2 is less than or equal to m?

I believe the given function should be location inside the "Merge" function of the Merge Sort.(Since we're merging a sorted array) Thank you for your time.

Image:

Edited: I'm thinking if n/2 is less than or equal to m, use the "Given" function . Otherwise, use the original "Merge" function (The usual Merge for Merge Sort)

share|improve this question
2  
cs.stackexchange.com – pinkpanther yesterday
3  
There is no relation. m is a given constant, n is the size of your input. n may be much larger than m. You probably should figure out how to merge arrays of size greater than m. – n.m. yesterday
1  
Thinking a bit more about it, I have no idea what they are talking about. They give you a unit that can merge fixed size lists in constant time. Yay! So what? Who can't do that? If they were distributing units with interesting asymptotic behaviour, that would be something. – n.m. yesterday
1  
Perhaps you and the poster of this exact same assignment should work together, as you're apparently in the same class. – Ken White yesterday
1  
@n.m.: I think that m is not a constant, and that they are positing units with interesting asymptotic behavior. I initially read it they way you did, but as your follow-up comment demonstrates, that reading doesn't really make sense. Instead, they must mean "a special functional unit that can merge two sorted lists in time m ^ {1-ϵ} for some 1 > ϵ > 0, where m is the size of the longer list". (That is, "two sorted lists of size at most m each" must mean "two sorted lists, with m denoting the size of the longest".) – ruakh yesterday
show 7 more comments

closed as not a real question by Michael Petrotta, Ken White, Luksprog, talonmies, alecxe yesterday

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.