010-2006

MO640 - Multiple-choice question

Two algorithms A and B solve a problem. For every input of size N,Algorithm A takes time f(N)=N², and Algorithm B takes time g(N)=aN, where a is a constant. We may conclude that: 

a) Algorithm A will always be faster than B, because A is quadratic, regardless of input size. 
b) Algorithm B will always be faster than A, because B is linear, regardless of input size. 
c) When the input size is smaller than a, the linear algorithm will be faster. 
d) When the input size is larger than a, the linear algorithm will be faster. 
e) NOTA 

Original idea by: Rodrigo Ritter.
Translation help by: Cristiano Borges Cardoso.