It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if anyone has researched the complexity of producing the algorithm itself. For example, if I have implemented a merge sort, I can quickly say that the run time is O(n log n), but suppose my input were actually something like "Your input will be a list of elements and a transitive, antisymmetric comparison operator. Output a list of those same elements in sorted order." Without already knowing a sorting algorithm, what is the complexity of producing an algorithm that meets those requirements and runs in O(n log n) time?