Question

A) What is the big O for the following:

f(n)=5n2+logn+1

i)n^2

ii)1

iii)logn

iv)5n2+logn+1

B) Given two algorithms with the following running time:Algorithm

A: Ta(n)=4n+20 andAlgorithm

B: Tb(n)=2n2+10Which of the following statements are correct?

i)Algorithm A is faster than algorithm B for n > 100.

ii)Algorithm B is faster than algorithm A for n > 100.

C) A function template can operate with:

i)an integer

ii)any type of data

iii)a string

iv)a Rectangle object

Answer 1

Answer A:

f(n) = 5n^2 + logn + 1

i) O(n^2) , because in a function f(n) = 5n^2 + logn + 1, n^2 provides the upper bound of the function. In simple words, n^2 is bigger than logn and 1 at any value of n.

Answer B:

i) Algorithm A is faster than algorithm B for n > 100

Explanation:

Ta(n)=4n+20

Tb(n)=2n^2+10

Now check the value of both the algorithms at a value greater than 100, let n = 110

Ta(n)=4n+20

Ta(n) = 4(110) + 20 = 440 + 20 = 460

Tb(n)=2n^2+10

= 2(110)^2 + 10 = 2 * 12,100 + 10 = 24,200 + 10 = 24,210

Here 460 < 24,210 that means algorithm A takes 460 time and Algortihm B take 24,210 time. Hence Algorithm A is faster than Algorithm B because Algorithm A takes less time than B.

Answer C:

ii)any type of data, Function templates that may deal for generic forms are feature models. This enables one to build a prototype of functions whose features can be applied to more than one type or class without repeating the whole code for each type.