Algorithm Question ?

[alien1]

I am having difficulty understand the solution behind a frequent exam question , any help would be greatly appreciated .

Question :

Two algorithms to solve a problem have complexities of
(i) 1/2 n ^ 2 and (ii) 20n for what value of n does algorithm (i) need less operations ?

Solution :

The complexity of an algorithm is the the number of operations / time units the algorithm requires as a function of the size of the problem n .
It is a function of n , f(n) .Algorithm (i) needs less operations if
1/2 n ^ 2 < 20 , or n^2 < 40 , or n < 4 .

I just dont understand where the answer is coming from or how it is calculated.

Thanks for your help ,

[Nominal Animal]

The question is, when is the following true:

1/2 n² < 20 n

Multiply both sides by 2 to get

n² < 40n

then divide by n (we can do that without worrying about possibly having to flip the <, because we know that n has to be positive), to get

n < 40

To verify, check the n = 39 case,

1/2 n² = 1/2 × 39² = 760.5
20 n = 20 × 39 = 780

and the n = 41 case,

1/2 n² = 1/2 × 41² = 840.5
20 n = 20 × 41 = 820

Remember, n is a positive integer. (A dataset cannot have a fractional number of entries, can it? No, n has to be a natural number.)

The fact that they happen to be equal at n = 40,

1/2 n² = 1/2 × 40² = 800
20 n = 20 × 40 = 800

just means that the two algorithms need equal number of operations at n = 40.

[alien1]

thanks that has cleared things up quite a bit : )