0
$\begingroup$

The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an external factor other than the input size, so , how may one construct a piecewise recursive function T on such an algorithm? How can a piecewise function T(n1,n2) (n1,n2 are the lengths of the lists) be defined when recursive calls do not depend on n1 or n2?

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. I see a description of the input (two inversely sorted lists), and a label for the operation to perform (merge). Please state explicitly in your question: assuming the output is to be a single list, any other conditions on it, like inversely sorted? What operations are defined for individual nodes, for lists, and what are the resource requirements? What does recursive calls depend on an external factor other than the input size mean? $\endgroup$ – greybeard Oct 23 '20 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.