Analysis of Algorithms and Arrays: Two Marks Important Questions and Answers

Data Structures using C ++

Chapter 3: Analysis of Algorithms and Arrays

Two Marks Questions with Answers

 

1. What are the drawbacks in using the standard unit of time, to measure the runtime of an algorithm?

Answer:

The runtime of an algorithm can not be measured in standard unit of time because in multiuser system running time depends on many factors such as –

1) System load

2) Number of other programs running

3) Instruction set used

4) Speed of underlying hardware

If we use standard unit of time such as seconds, milliseconds, minutes and so on for measuring the runtime of algorithm then we get varied result for same set of input data. Hence the time complexity given in terms of frequency count.

2. What are the measures that are used to measure the complexity of an algorithm?

Answer:

The time complexity and the space complexity are the two measures that are used to measure the complexity of an algorithm.

3. Write the concept of time and space complexity.

OR

How do you measure the efficiency of an algorithm.

Answer:

Time complexity is the amount of time required by an algorithm to execute. For computing the time complexity the frequency count of the basic operation in the algorithm is computed. This frequency count is then denoted in terms of asymptotic notations to express the time complexity of an algorithm. The space complexity is an amount of space required by an algorithm. The space complexity is denoted in terms of asymptotic notations.

4. Differentiate time complexity from space complexity.

Answer:

Time complexity is amount of time required by a program to execute.

The space complexity is amount of space required by a program to execute.

5. Establish the relation between O and Ω.

Answer:

The notation O represents the upper bound of algorithm's running time. The omega notation Ω represents the lower bound of algorithm's running time.

The theta notion represents the running time between upper and lower bound. If f(n) and g(n) are two functions then, f(n) = Ө (n) if and only if f(n) f(n) = O (g(n)) and f(n) = Ω g(n)).

6. If f(n) = a_mn^m +..... a₁n+a₀, then prove that f(n) = O(n^m).

Answer:

Let,

f(n) = a_mn^m + a_m‒1n ^m‒1 + a_m‒2n^m‒2 +...+a₀

If we treate aⁱ_m as a constant then the equation (1) becomes

Thus neglecting the constant term we will have

f(n) = O(n^m)

7. Using the step count method analyze the time complexity when 2 m x n matrices are added.

Ans. :

For computing the step count for the matrix addition, consider the following code ‒

1. for (i ←0; i < m; i++)

2. {

3.          for (j 0; j < n; j++)

4.        {

5.                C[i][j] = A[i][j] + B[i][j]

6.        }

7. }

Statement                   Step count

i←0                                ‒    1

i<m                                 ‒   m + 1

i ++                                ‒     m

j←0                                ‒    m

j←n                               ‒    (n + 1) m

j++                                 ‒    (n + 1) m

C[i][j]=A[i][j] + B[i][j] ‒    n(m)

Total                                  3mn + 5m + 2

By neglecting constants, the time complexity = O(mn)

8. An array has exactly n nodes. They are filled from the set {0, 1, 2, ..., n − 1, n}. There are no duplicates in the list. Design an O(n) worst case time algorithm to find which one of the elements from the above set is missing in the array.

Ans  :

Algorithm: GetMissing (Array a[0..n])

{

   total = (n + 1) * (n + 2)/2   //Finding sum of all the elements from 0 to n

           for (i← 0 to n) do

           total ‒ = a[i]     //subtracting each number from total

           return total        // Remaining will be missing element

}

9. What is the best,worst and average case time complexities of linear search algorithm?

Answer:

The O(n) is the best,worst and average case time complexity of linear search algorithm.

10.  Define Big oh notation.

Answer:

Let f(n) and g(n) be two non‒negative functions.

Let n₀ and constant c are two integers such that n₀ denotes some value of input and n> n₀. Similarly c is some constant such that c > 0. We can write

f(n)≤ c*g(n)

then f(n) is big oh of g(n). It is also denoted as f(n) ϵ O (g(n)). In other words f(n) is less than g(n) if g(n) is multiple of some constant c.

11. Define Big omega notation.

Answer:

A function f(n) is said to be in Ω (g(n)) if f(n) is bounded below by some positive constant multiple of g(n) such that

f(n) ≥ c* g(n)             For all n ≥ no

It is denoted as f(n) ϵ Ω (g(n)). Following graph illustrates the curve for Ω notation.

12.  Define Big theta notation.

Answer:

Let F(n) and g(n) be two non negative functions. There are two positive constants namely c₁ and c₂ such that

 c₁ ≤ g(n) ≤ c₂ g(n)

Then we can say that

f(n) ϵ Ө (g(n))

13. List the asymptotic classes in increasing order.

Answer:

1. Constant(1)

2. Logarithmic(log n)

3. Linear(n)

4. n log n

5. Quadratic (n²)

6. cubic(n³)

7. Exponential((2ⁿ)

8. Factorial(n!)

14. The (log n)th smallest number of n unsorted numbers can be determined in O(n) average, case time (True/False)

Answer:

False. The (log n)th smallest number of n unsorted numbers can be determined in O(n) worst‒case time.

15. Compare the orders of growth of n(n‒1)/2 and n².

Ans. :

For comparing the orders of growth of n(n‒1)/2 and n² we consider some sample values of n.

16. Give the time complexity 1 + 3 + 5 + 7 + ... + 999.

Answer:  

Hence time complexity is O(n)².

17. How to measure an algorithm's running time?

Answer:

To measure the algorithm's running time, its basic operation is identified. Then the frequency count of this basic operation is calculated. And finally applying the asymptotic notations for basic operations, the time complexity is calculated.

18. What do you mean by "Worst case efficiency" of an algorithm ?

Answer:

Worst case time complexity is a time complexity when algorithm runs for a longest time.