TDD is not about testing, it's about design.
Far from falling apart with complexity, it excels in these circumstances. It will drive you to consider the larger problem in smaller pieces, which will lead to a better design.
Do not set out to try to test every permutation of your algorithm. Just build test after test, write the simplest code to make the test work, until you have your bases covered. You should see what I mean about breaking the problem down because you will be encouraged to fake out parts of the problem while testing other parts, to save yourself having to write 10 billion tests for 10 billion permutations.
Edit: I wanted to add an example, but didn't have time earlier.
Let's consider an in-place-sort algorithm. We could go ahead and write tests which cover the top end of the array, the bottom end of the array and all sorts of weird combinations in the middle. For each one, we would have to build a complete array of some kind of object. This would take time.
Or we could tackle the problem in four parts:
- Traverse the array.
- Compare selected items.
- Switch items.
- Coordinate the above three.
The first is the only complicated part of the problem but by abstracting it out from the rest, you have made it much, much simpler.
The second is almost certainly handled by the object itself, at least optionally, in many static-typed frameworks there will be an interface to show whether that functionality is implemented. So you don't need to test this.
The third is incredibly easy to test.
The fourth just handles two pointers, asks the traversal class to move the pointers around, calls for a compare and based on the result of that compare, calls for the items to be swapped. If you've faked out the first three problems, you can test this very easily.
How have we led to a better design here? Let's say that you've kept it simple and implemented a bubble sort. It works but, when you go to production and it has to handle a million objects, it is far too slow. All you have to do is write new traversal functionality and swap it in. You don't have to deal with the complexity of handling the other three problems.
This, you will find, is the difference between unit testing and TDD. The unit tester will say that this has made your tests fragile, that if you had tested simple inputs and output then you wouldn't now have to write more tests for your new functionality. The TDDer will say that I have separated concerns suitably so that each class I have does one thing and one thing well.