I believe the worst-case asymptotic time complexity of spaghetti sort is O(n^2). The algorithm works for any input list, so I will pick a hard class of inputs:

I believe the worst-case asymptotic time complexity of spaghetti sort is O(n^2). The algorithm works for any input list, so I will pick a hard class of inputs: The list shall be some permutation of [1, 2, 3, ..., n]. The sum of the spaghetti lengths is 1+2+3+...+n, which is in O(n^2). You need to spend O(n^2) effort to gather the flour to make the spaghetti. Hence this sets a lower bound on the overall algorithm.