running time of two programs run separately and then together

Together they take 2 minutes to complete

In this case, I think that each program is fully CPU-bound and can saturate 100% of the CPUs available on the machine. Therefore when the programs run together, each runs at half speed.

It's also possible that this would be the observed behavior if both programs were able and willing to saturate some other resource apart from the CPU, for example some I/O device. However, since in practice, usually the performance of I/O devices does not decrease linearly with the load applied to them if they are oversaturated, I would consider that a less likely scenario and go with CPU-bound as a first guess.

Together they take 1 minute to complete

The two programs do not contest the same resources, or there are ample resources in the system to satisfy the demands of both. Therefore, they end up not interfering with each other.

Together they take half a minute to complete

The programs operate on the same input, and both can tell when all input is used up, so each ends up doing half the work it would do if launched alone at half the running time. Also, the system obviously has the capacity to supply double the amount of whatever resource these programs are constrained by.

Since in this case the running time decreases linearly with the amount of processes (perfect scaling), it seems more likely that the resource constraining the programs is CPU for the same reasons explained in the "2 minutes" scenario. This also fits in well with the "common input" assumption, as the input would not be very likely to be coming from one source if there were e.g. different I/O devices supplying it.

Therefore, the first guess in this case is that each program is CPU-bound and written such that it consumes at most half the CPU resources in the system.

For A, They're programs that are in competition for a mutually exclusive resource.

For B, They're independent programs that don't really interact.

For C, which is the one you're struggling with, it seems they both have the same work to pick from. For example, there's a queue of tasks to do, both programs are capable of doing the tasks, and they know what tasks have been done. So if they both run at the same time (assuming multi core machine, but even then not necessarily, all that's important is that they don't have a resource bottleneck) they get the work done in half the time.

See Performance in multithreaded Java application for another possible reason why processes can run faster when you have more than one.

Although I admit that the queue of tasks that canbeperformed concurrently is a much simpler reason to explain this reduced running time.