Posted on February 6, 2013

Ever since I started studying Computer Science I have struggled to find a good way to differentiate it from mathematics. Mathematicians use computers. Mathematicians even write code. Computer scientists certainly prove things, well at least some of them. And they definitely use mathematics. So what is the difference?

I think today I found my answer. I was re-reading my data structures textbook for fun and found my answer. It was nestled in there between a discussion of selection sort and shell sort. Just a little musing by the author. The discussion was on lower bounded algorithms and how their analysis is difficult. Why is it difficult? For a computer scientist to prove all sorting algorithms are bounded below by big-omega of n-squared, on average with adjacent exchange of elements,would require running all of the possible algorithms of this kind.

If you try to do this you will fail, because there are infinitely many ways to do this ( some will argue). At least in theory there seems to be. I think you could verify it for a given time period because a lack of known possible technologies. So you could configure your hardware in a very large known possible number of ways, to get this finite approximation. However every time new technology is discovered, you would have to add to the possible permutations. But that’s not the point. (Just an aside).

The point is, a computer scientist is not satisfied until they actually run an experiment on a computer. In fact, they aren’t satisfied until they run a lot of experiments on a computer. Whereas for a mathematician, the proof is enough. The proof in fact, is the proof that something is true or not. Whereas the computer scientist requires physical results. This seems to me a curious fact.

I think this is why computer scientists refer to themselves as scientists, because CS is an experimental science. Mathematics is too, in the sense that both disciplines play with thought experiments. Mathematicians simply choose to do their thought experiments on paper, where as computer scientists prefer screens.