Page 42 - DCAP407_DATA_STRUCTURE

Unit 2: Complexity Analysis

• Usually, the efficiency or running time of an algorithm is stated as a function which relates the
input length to the time complexity or space complexity.

• The efficiency of some algorithms may vary for inputs of the same size. For such algorithms, we
need to differentiate between the worst case, average case and best case efficiencies.
2.5 Keywords

Lower Bound: A mathematical argument which means that you can't hope to go faster than a certain
amount.
Memory: An internal storage area in the computer.
Notation: The activity of representing something by a special system of characters.
Upper Bound: A number equal to or greater than any other number in a given set.

2.6 Self Assessment
1. State whether the following statements are true or false:
(a) An algorithm is a set of instructions that performs a particular task.

(b) The efficiency of each algorithm can be checked by computing its space complexity.
(c) Summation is the operation of combining a sequence of numbers using addition.
(d) Factorial function means to multiply a series of descending natural numbers.
(e) Time space tradeoff in context with algorithms relates to the execution of an algorithm.
(f) Variable space requirement is the amount of space acquired by fixed size structure, variables
and constants.
2. Fill in the blanks:
(a) The ………………………… help to represent the time complexity in a shorthand way.
(b) ………………………… is generally used to express an ordering property among the
functions.

(c) A good algorithm must have ………………………… number of space complexity.
(d) The …………………………describes the way algorithm performs in the best case time
complexity.
(e) If an algorithm takes maximum amount of time to execute a specific set of input, then it is
called the …………………………
3. Select a suitable choice for every question:
(a) Which of the following is used to express the space complexity of an algorithm?
(i) Theta notation (ii) Big-O notation (iii) Omega notation (iv) Factorial function
(b) Which of the following provides an algorithm’s behavior on a typical or random input?
(i) Best case analysis (ii) Average case analysis (iii) Floor function (iv) Ceiling function

(c) Which of the following is called a greatest integer function?
(i) Ceiling function (ii ) Floor function (iii) Modular arithmetic (iv) Factorial
(d) Which of the following is an important part of computational complexity theory?
(i) Algorithm analysis (ii) Floor function (iii) Ceiling function (iv) Time space tradeoff
(e) Which of the following can be defined as “f(n)≥ c∗ g(n)”?
(i) Big-O notation (ii) Theta notation (iii) Omega notation (iv) Floor function

LOVELY PROFESSIONAL UNIVERSITY 35