Suppose we have three algorithms Algorithm A Algorithm B and

Suppose we have three algorithms, Algorithm A, Algorithm B, and Algo-rithm C. All of the solve the same problem, taking as input a list of n elements and producing the same output. Suppose

Algorithm A requires (n log n + 2n)(n^2 log(n) + 34n) operations

Algorithm B requires ([log(n)]^2 + n + 100)(2^n + n) operations, and

Algorithm C requires 17 + 46n + 3n operations.

List the algorithms from most ecient to least ecient, and justify youranswe

Solution

The order of magnitude for any algorithm is:

O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(n^3)<O(2^n)

where O(1) is best case and O(2^n) is worst

Now lets start with each option

1) Algorithm A

(n log n + 2n)(n² log n + 34n) -> (n log n)(n² log n) +  (n log n) (34n) + (2n) (n² log n) + (2n) (34n)

-> n³ log²n +34 n² logn + 2n³ log n + 68 n ²

   ^-> 3n³ log²n + 34 n² logn + 68 n ²

-> O(n³)

2) Algorithm B

([log(n)]^2 + n + 100)(2^n + n) -> ([log(n)]^2)(2ⁿ) +  ([log(n)]^2) (n) + (n)(2ⁿ)+ (n)(n) + 100(2ⁿ) + 100 (n)

-> ([log(n)]^2)(2ⁿ) + n ([log(n)]^2) +n (2ⁿ) + n² + 100(2ⁿ) +100 (n)

->O(2ⁿ)

3) Algorithm C

17 + 46n + 3n -> 17 + 46n +3n

-> 17 + 49n

-> O(n)

So,the order is C,A,B

c = most efficient

a = medium efficient

b = least efficient