The time complexity of self-assembly

Time efficiency of self-assembly is crucial for many biological processes. Moreover, as larger and ever more complex nanostructures are to be realized for technological or medical applications, time efficiency in artificial self-assembly becomes vital. In computer science, the concept of time complexity is used to characterize the efficiency of an algorithm and to classify computational problems according to their degree of difficulty. This parameter describes how an algorithm’s runtime depends on the size of the input data. Here we characterize the time complexity of self-assembly processes by exploring how the time required to realize a certain, substantial yield of a given target structure scales with its size. We identify distinct classes of assembly scenarios, i.e. ‘algorithms’, to accomplish this task, and show that they exhibit drastically different degrees of complexity. Based on our analysis, we suggest a fully irreversible scheme for the artificial self-assembly of nanostructures, which complements the state-of-the-art approach using reversible binding reactions and requires no fine-tuning of binding energies.