most people would consider the so-called "linear" algorithm exponential, as the size of the input for the number n is m = Theta(log(n)) bits; the running time is Theta(2^m). the "quadratic" running time is Theta(4^m).