- A data structure is a logical method of representing data in memory.
- Data structure is strictly described as an instance of an Abstract Data Type (ADT).
- An Abstract Data Type is defined as a mathematical model of a user-defined type along with the operations performed on that model.
|Array||Fast access if index is known||Slow search, fixed size|
|Stack||Features last in – first out access||Slow access to other elements|
|Queue||Features first in – first out access||Slow access to other elements|
|Linked list||Quick insertion and deletion||Slow search|
|Binary tree||Quick insertion, deletion and search when tree is balanced||Deletion procedure is complex|
|Hash table||Fast insertion and access if key is known||Inefficient memory usage, slow access if key is not known|
|Heap||Fast insertion, deletion and access to largest element||Slow access to other elements|
|Graph||Simulates real world problems||Some algorithms are slow and complex|
An algorithm can be described as sequence of steps or instructions required to solve a given problem.
It is a finite set of instructions written to accomplish a particular task.
When designing an algorithm, one must ensure that the
algorithm adheres to the following criteria:
Input: Some input data (can be empty in some cases) externally supplied to the algorithm
Output: At least one output is produced
Finiteness: The algorithm must terminate after finite number of steps
Definiteness: The instructions must be clear and unambiguous
Effectiveness: Every instruction must be basic enough to be carried out on paper
Following are certain points to be considered
while writing an algorithm :
Representing an algorithm.
Designing an algorithm.
Analyzing an algorithm.
Algorithm Analysis involves comparing different algorithms written for a specific problem. All the algorithms are compared for their space and time complexities.
Space complexity: It refers to the amount of storage the algorithm consumes.
Time complexity: It is the time required by the algorithm for execution.
Following are the different types of time complexities:
Best-case time complexity: It is the measure of minimum time required for an algorithm to execute for a known input size.
Average case time complexity: Average time complexity is the measure of time an algorithm will require to execute, for a typical input data size. This method requires statistical calculations.
Worst-case time complexity: It is the measure of maximum time required for an algorithm to execute for a known input size.