The Math of Asymptotics Solve the two following problems: Algorithm A uses 8n primitive operations...

Question

2. The Math of Asymptotics
Solve the two following problems:
• Algorithm A uses 8n primitive operations, while Algorithm B uses n2 primitive operations. Determine the value n0 such that A runs faster than B for all n ≥ n0.
• Algorithm A uses 10n primitive operations, while Algorithm B uses 2nlog n prim- itive operations. Determine the value n0 such that A runs faster than B for all n ≥ n0.
• Algorithm A uses 10nlog n primitive operations, while Algorithm B uses n2 prim- itive operations. Determine the value n0 such that A runs faster than B for all n ≥ n0.
Remark: log n stands for log2 n (logarithm in base 2 of n).

Answer 1

8 n < n ²

<=> n ² - 8 n > 0

<=> n ² - 8 n + 16 > 16

<=> ( n - 4 ) ² > 16

<=> | n - 4 | > 4

<=> n - 4 > 4 OR - n + 4 > 4

<=> n > 8 OR n < 0

Since n < 0 is meaningless concerning the given problem, the (only) solution is:

n₀ > 8

 

10 n < 2 n log n

<=> 5 < log n

<=> 2 ⁵ < n

<=> n > 2 ⁵ =  32

Solution is: n₀  > 32

 

10 n log n < n ²

<=> 10 log n < n 

<=> log n < n / 10

<=> n < 2 ^{n / 10}

<=> n ¹⁰ < 2 ⁿ

<=> ...

This can not be calculated in closed form.
Using a numerical algorithm (or just the method of trial and error) gives:

n₀ ≥ 59