Data Structures

1 What is Data Structure
Data Structure is a representation of logical relationship existing between individual elements of data. In other words, a data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.
It is a mathematical or logical model for particular organization of data items.
It mainly specifies the following things:-
1. Organization of data
2. Accessing methods
3. Processing alternatives for information

1.1 Classification of Data Structures
Data structures are normally divided into two categories: -
1. Primitive Data Structure:- These are basic structures and are directly operated upon by the machine instructions.
2. Non-primitive Data structure:- These are derived from primitive data structures. It emphasize on structuring of a group of homogeneous or heterogeneous data items.

1.2 Operations on Data structure
The design of an efficient data structure must take operations to be performed on the data structure into account. The data structure is to be manipulated in a number of major program functions. After evaluating the operations to be performed on the data structure, an abstract data type is defined to use it in subsequent programs.
The most commonly used operations on data structure are :
1. Creation
2. Insertion
3. Deletion
4. Selection
5. Updation
6. Searching
7. Sorting
8. Merging

1.3 Algorithms
An algorithm is any well- formed –defined computational procedure that takes some value or set of values as input and procedure some values or set of values as output.

1.4 Analyzing algorithms
Analyzing an algorithm measuring computational time and memory space required during execution.

1.5 Performance analysis & measurement

1.5.1 Space complexity
The space complexity of a program is the amount of memory it needed to fun to completion.
1.5.2 Time Complexity:
It is the amount of computer time needs to run to completion.

1.6 Big OH Notation
Big OH is a characterization scheme that allows to measure properties of algorithm complexity performance and/or memory requirements in a general fashion.

1.7 Categories of Algorithms
Based on Big OH notation the algorithms can be categorized as follows:
• Constant time (O(1)) algorithm.
• Logarithmic time (O(log n)) algorithms.
• Linear time (O(n)) algorithms.
• Polynomial time (O(n**k),for k >1) algorithms
• Exponential time (O(k**n), for k >1) algorithms.
• Many algorithms are O(n log n).