With an RBF Kernel, you are stuck solving the dual problem which has O(n^2 * m) complexity. With the linear kernel, you can solve the primal scales with O(n*m) complexity.