Spades does not have an easytoexpress bounded time complexity; it's too complicated. You can only do that for fairly simple algorithms. A basic kmerbased assembler has a time complexity of O(n+m) where n is the amount of input data and m is the number of unique kmers. But, Spades has a lot of different phases, each with different characteristics, and it's hard to know which one will be the slowest. Graphtraversing algorithms especially can have worstcase bounds that are very different from what happens in a normal genome.
I'm not really sure about blastn, but full SmithWaterman is O(mn) for two sequences of length m and n, and banded is O(b(m+n)) where b is the bandwidth. Blast uses some heuristics to reduce those so it may scale somewhat differently.
Last edited by Brian Bushnell; 01292016 at 09:28 PM.
