Recommendation letter from CS faculty for math grad school (and vice versa)
As a general principle, you want letters of recommendation from the professors who know your best work best. Letters from professors in fields closely related to yours are OK. (Applied) math and (theoretical) CS surely qualify.
In this case you should certainly have one from this professor. The professor would probably write slightly different letters for math or cs graduate programs - you can ask about that.
Good luck.