Question

There are two algorithms that perform a particular task. Algorithm 1 has a complexity function: f(n) = 5n + 50. Algorithm 2 has a complexity function g(n) = n^2 + 10g . (Show your answer)

a)Which algorithm is more efficient when n = 5?

b) Which algorithm is more efficient when n = 20?

c) what are complexity of f(n) and g(n)

Answer 1

Note:

According to the question g(n) = n^2 + 10g, but g is not defined. So, it is either n or misprinted.

I'll be solving both the solution:

f(n) = 5n + 50

g(n) = n² + 10n

Ans a) We are given n=5, so we'll calculate the value of f(5) and g(5), and the function which will return the minimum value will be more efficient.

f(5) = 5*5 + 50 = 75

g(5) = 5² + 10*5 = 25 + 50 = 75

Both the function is returning the same value hence, for n=5 both the algorithms are efficient.

Ans b)

We are given n=5, so we'll calculate the value of f(20) and g(20), and the function which will return the minimum value will be more efficient.

f(20) = 5*20 + 50 = 150

g(20) = 20² + 10*20 = 400 + 200 = 600

The value returned by f(20) is less than the value returned by g(20). Hence, f(n) is more efficient when n=20.

Ans c) Complexity of f(n)

f(n) = 5n + 50

We can see that the Highest factor of n in the function is 1. So the complexity of f(n) is O(n) or more precisely (n).

g(n) = n² + 10n

We can see that the Highest factor of n in the function is 2. So the complexity of g(n) is O(n²) or more precisely (n²).

Note the complexity of g(n) is greater than the f(n). Hence for large values g(n) is much better than f(n).

***************************************************************************************************

If g(n) = n² + 10

f(n) = 5n + 50

g(n) = n² + 10

Ans a) We are given n=5, so we'll calculate the value of f(5) and g(5), and the function which will return the minimum value will be more efficient.

f(5) = 5*5 + 50 = 75

g(5) = 5² + 10 = 25 + 10 = 35

The value returned by g(5) is less than the value returned by f(5). Hence, g(n) is more efficient when n=5.

Ans b)

We are given n=5, so we'll calculate the value of f(20) and g(20), and the function which will return the minimum value will be more efficient.

f(20) = 5*20 + 50 = 150

g(20) = 20² + 10 = 400 + 10 = 410

The value returned by f(20) is less than the value returned by g(20). Hence, f(n) is more efficient when n=20.

Ans c) Complexity of f(n)

f(n) = 5n + 50

We can see that the Highest factor of n in the function is 1. So the complexity of f(n) is O(n) or more precisely (n).

g(n) = n² + 10

We can see that the Highest factor of n in the function is 2. So the complexity of g(n) is O(n²) or more precisely (n²).

Note the complexity of g(n) is greater than the f(n). Hence for large values g(n) is much better than f(n).

Leave a comment if face any doubt!!!!