How to judge the relative efficiency of algorithms given runtimes as functions of 'n'?

Question

Consider two algorithms, A, and B. These algorithms both solve the same problem, and have time complexities (in terms of the number of elementary operations they perform) given respectively by

a) (n) = 9n+6

b) (n) = 2(n^2)+1

(i) Which algorithm is the best asymptotically?

(ii) Which is the best for small input sizes n, and for what values of n is this the case? (You may assume where necessary that n>0.)

I think it's A. Am I right?

And what's the answer for part B? What exactly do they want?

Answer 1

Which algorithm is the best asymptotically?

To answer this question, you just need to take a look at the exponents of n in both functions: Asymptotically, n² will grow faster than n. So A ∈ O(n) is asymptotically the better choice than B ∈ O(n²).

Which is the best for small input sizes n, and for what values of n is this the case? (You may assume where necessary that n>0.)

To answer this question, you need to find the point of intersection where both functions have the same value. And for n=5 both functions evaluate to 51 (see 9n+6=2(n^2)+1 on Wolfram Alpha). And since A(4)=42 and B(4)=33, B is the better choice for n < 5.

Answer 2

I think plotting those functions would be very helpful to understand what's going on.

Answer 3

You should probably start by familiarizing yourself with asymptotics, big O notation, and the like. Asymptotically, a will be better. Why? Because it can be proven that for sufficiently large N, a(n) < b(n) for n> N.

Proof left as an exercise for the reader.