> a linear algorithm that does N+1 queries.

That's what quadratic means.