Page 35 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes 2.5 Keywords

Algorithm Complexity: The complexity of an algorithm is a function describing the efficiency of
the algorithm in terms of the amount of data the algorithm must process.

Algorithm: An algorithm is a clearly specified set of simple instructions to be followed to solve
a problem.
Big O: "Big O" refers to a way of rating the efficiency of an algorithm.

Constant Time: This means that the algorithm requires the same fixed number of steps regardless
of the size of the task.
Insertion Operation: Insertion operation is used for adding a new element to the list.

Linear Time: This means that the algorithm requires a number of steps proportional to the size
of the task.
Space Complexity: Space complexity is a function describing the amount of memory (space) an
algorithm takes in terms of the amount of input to the algorithm.
Time Complexity: Time complexity is a function describing the amount of time an algorithm
takes in terms of the amount of input to the algorithm.

2.6 Review Questions

1. Discuss the use of various data structure operations.
2. What is an algorithm? Discuss the process of analyzing algorithms.
3. Illustrate the use of running time in analyzing algorithm.

4. Explain the concept of algorithm complexity.
5. Describe the main complexity measures of the efficiency of an algorithm.
6. There is often a time-space-tradeoff involved in a problem. Comment.

7. What is Big O notation? Discuss with examples.
8. Define some theorems which can be used to simplify big O calculations.
9. Discuss the asymptotic behavior of the growth rate functions.
10. Discuss the various properties of Big O notation.

Answers: Self Assessment

1. Insertion 2. Sorting

3. algorithm 4. Model
5. complexity 6. Time complexity
7. Space complexity 8. Big O
9. O(g(n)) 10. linear time

11. quadratic time 12. n log n
13. n log n 14. transitive

28 LOVELY PROFESSIONAL UNIVERSITY