It is entirley possible that after doing this your program will only run twice as fast (because you had to redesign the algorithm to make it parallelizable) on a processor with four cores, which is great, except what if someone with only one processor tries to run the code? It would run twice as slow! .
That's not true. While multi-threading has some overhead, it is extremely small unless you are trying to create thousands of threads. A single core processor would not have a noticeable difference between running a process multi-threaded or only as a single thread. The problem is the same whether you thread it or not, and it still takes the same number of processor operations. On a single core, it will simply switch between the threads based on thread priority however this switching is very fast, thus it will emulate a single thread application on a single core. However, if you can dispatch each of these threads to 2 or 4 cores, the execution time will dramatically decrease.
So, multi-threading is almost strictly better, why doesn't everyone do it? It's more difficult to code. Which means more money spent on projects and for things such as games, where processor performance generally isn't a bottleneck, there simply isn't a justification for the cost to code a program multi-threaded vs single thread.
However, this is slowly changing with the addition of extremely complex physics as seen (or we will see) with companies such as Valve and Remedy.