Page 23 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures Anil Sharma, Lovely Professional University

Notes Unit 2: Data Structure Operations and
Algorithms Complexity

CONTENTS
Objectives

Introduction
2.1 Operations on Data Structures
2.2 Algorithm Complexity
2.3 Big O Notation

2.3.1 Growth Rate Functions
2.3.2 Properties of Big O
2.3.3 Lower Bounds and Tight Bounds
2.3.4 More Properties

2.4 Summary
2.5 Keywords
2.6 Review Questions
2.7 Further Readings

Objectives

After studying this unit, you will be able to:
Discuss various operations on data structures
Explain algorithm complexity

Discuss Big O notation
Introduction

Data are processed by means of certain operations which appearing in the data structure. Data
has situation that depends largely on the frequency with which specific operations are performed.
An essential aspect to data structures is algorithms. Data structures are implemented using
algorithms. In this unit, we will introduce some of the most frequently used operations. Also we
will discuss the concept of algorithm complexity.

2.1 Operations on Data Structures

We may perform the following operations on any linear structure, whether it is an array or a
linked list.

Traversal: By means of traversal operation, we can process each element in the list.
Search: By means of this operation, we can find the location of the element with a given
value or the record with a given key.

16 LOVELY PROFESSIONAL UNIVERSITY