  We present a method for synthesizing recursive functions that satisfy both a
functional specification and an asymptotic resource bound. Prior methods for
synthesis with a resource metric require the user to specify a concrete
expression exactly describing resource usage, whereas our method uses big-O
notation to specify the asymptotic resource usage. Our method can synthesize
programs with complex resource bounds, such as a sort function that has
complexity O(nlog(n)). Our synthesis procedure uses a type system that is able
to assign an asymptotic complexity to terms, and can track recurrence relations
of functions. These typing rules are justified by theorems used in analysis of
algorithms, such as the Master Theorem and the Akra-Bazzi method. We
implemented our method as an extension of prior type-based synthesis work. Our
tool, SynPlexity, was able to synthesize complex divide-and-conquer programs
that cannot be synthesized by prior solvers.
