I don't think that it's useful to differentiate logistic regression and softmax based on your terms. This is because you don't choose one or the other based on performance/computational requirements/ease of calculation of derivatives/...
The fact is that you use one or the other based on which is your problem.
If you need to recognize cat pictures vs. non-cat pictures you will use logistic regression (even with a very complex NN the last step will be always a logistic regression). Of course, you could use softmax but the outputs will be redundant, i.e. one output will always be one minus the other.
If you need to recognize cat pictures vs. dog pictures vs. other pictures you will use softmax. Note that, in order to use softmax, you need to have only mutually exclusive classes. Mutually exclusive classes mean that an example cannot belong to multiple classes. What if a picture represents both a dog and a cat? In this case, it should be marked as other picture. If you want to avoid these you could use one more class to denote pictures with both cats and dogs.
However, if you want to recognize cats, dogs, birds, fishes, boats, houses, etc. the number of mixed classes that you need to include will grow very fast. When you are dealing with non-mutually exclusive classes you should use multitask learning. In this case, the sum of the outputs is no longer 1. In the simplest case, you could think of multitask learning as a shared NN where the last step is made by multiple logistic regression. In more complex cases the last step could be made by a combination of different softmax and logistic regressions.
- If you need to use non-mutually exclusive classes use multitask learning. Eventually, you will use in multitask learning softmax regression and/or logist regression.
- If you need to use more than two mutually exclusive classes use softmax regression.
- If you need to use only two exclusive classes use logistic regression.