I did a simple test for KNN written in C.
testing 100 points with 520000 training needs about 61sec
with optimization it can be done in 31sec (k = 9)
(-O -mcpu=pentium4)
in that sense, 5-cv + testing can be done in 50 hours if
optimized. Otherwise, seems it needs 100 hours or so.