Data structure -UNIT-I
Data structure definition:
A data structure is a way of organizing and storing data in a computer so that it can be accessed and
used efficiently.
or
A data structure is a specialized format for organizing, processing, storing, and retrieving data
efficiently. It defines the relationship between data elements and the operations that can be performed
on them.
Just like you'd organize your room for easy access to your belongings, data structures help organize
information within a computer program so that it can be:
Stored and retrieved efficiently: This means faster programs and smoother user experiences.
Manipulated and processed easily: You can add, delete, search for, or sort data much more effectively.
Scalable: When dealing with large amounts of data, a well-chosen data structure keeps performance
high.
Key characteristics
Organizes data: They provide a structured way to store information.
Defines relationships: They show how different pieces of data are connected.
Supports operations: They allow you to perform specific actions like adding, deleting, finding, or
sorting data.
Algorithm:
An algorithm is a finite set of well-defined, unambiguous instructions to solve a specific problem or
perform a computation. It outlines the logical steps and operations required to achieve a desired output
from a given input. Algorithms are independent of any specific programming language and can be
expressed in various forms, such as pseudocode or plain language.
Its key characteristics ensure its effectiveness and utility:
Finiteness:
An algorithm must terminate after a finite number of steps. It cannot run indefinitely.
Definiteness/Unambiguity:
Each step of an algorithm must be precisely defined and unambiguous. There should be no room for
multiple interpretations of an instruction.
Input:
An algorithm takes zero or more well-defined inputs, which are the quantities supplied for processing.
Output:
An algorithm produces one or more well-defined outputs, which are the results of the computation.
Effectiveness:
Every instruction in an algorithm must be sufficiently basic and executable in a finite amount of time,
using available resources.
Feasibility:
The algorithm should be practically implementable with the available resources and technology.
Generality:
An algorithm should ideally be applicable to a range of inputs or a class of problems, rather than being
limited to a single specific case.
Language Independence:
The design and logic of an algorithm should be independent of any specific programming language. It
should be expressible in a way that can be translated into various languages.
Flow chart:
A flowchart is a diagram that visually represents the steps, sequences, and decisions involved in a
process or workflow. It uses symbols and arrows to illustrate how one step leads to the next,
making complex processes easier to understand and analyze. Flowcharts are widely used in
various fields for planning, documenting, and improving processes.
Key aspects of a flowchart:
Visual representation:
Flowcharts use shapes and symbols to represent different types of actions, decisions, and data
inputs/outputs.
Sequential flow:
Arrows indicate the direction and order of steps in the process, showing how one step leads to the next.
Standardized symbols:
Common symbols include ovals for start/end points, rectangles for processes, diamonds for decisions,
and parallelograms for input/output.
Versatility:
Flowcharts can be simple or complex, ranging from basic hand-drawn diagrams to comprehensive,
computer-generated visuals.
Uses of flowcharts:
Process documentation:
Flowcharts can be used to document and explain how a process works, making it easier for
others to understand and follow.
Process improvement:
By visualizing the process, flowcharts can help identify bottlenecks, inefficiencies, and areas where
improvements can be made.
Training and onboarding:
Flowcharts can be used to train new employees or explain a process to someone unfamiliar with it.
Decision-making:
Flowcharts can help visualize the decision points in a process and the different paths that can be taken
based on those decisions.
The eight basic symbols commonly used in flowcharts are: oval (or terminator), rectangle (or
process), diamond (or decision), parallelogram (or input/output), arrow (or flowline), circle (or
on-page connector), triangle (or merge symbol), and upside-down triangle (or off-page
connector).
Complexity of an algorithm:
The complexity of an algorithm refers to the measure of the resources required by the algorithm to
solve a problem or perform a task, typically as a function of the size of the input. The two primary
types of complexity are:
Time Complexity:
This measures the amount of time an algorithm takes to complete its execution as the input size
grows. It is usually expressed using Big O notation, which describes the upper bound on the
growth rate of the algorithm's execution time in the worst-case scenario. For example, O(n)
indicates that the time taken grows linearly with the input size n, while O(n^2) indicates a
quadratic growth.
Space Complexity:
This measures the amount of memory space an algorithm requires to execute, also as a function
of the input size. It encompasses both the space used for storing the input data and any auxiliary
space used for temporary variables or data structures during the algorithm's execution. Like
time complexity, it is often expressed using Big O notation.
Analyzing the complexity of an algorithm helps in understanding its efficiency and scalability,
allowing for comparisons between different algorithms and the selection of the most suitable one
for a given problem and input size.
In the context of data structures and algorithms, "order of complexity" refers to the asymptotic
growth rate of an algorithm's resource consumption (typically time or space) as the input size
increases. It is primarily expressed using Big O notation, which provides an upper bound on this
growth.
Here's a breakdown:
• Time Complexity:
This measures how the execution time of an algorithm scales with the input size (denoted as 'n').
• Space Complexity:
This measures how the memory usage of an algorithm scales with the input size.
Key aspects of "order of complexity":
• Big O Notation (O):
The most common notation, it describes the upper bound or worst-case scenario of an
algorithm's performance. It focuses on the dominant term in the function representing the
resource consumption, ignoring constant factors and lower-order terms.
• Examples:
• O(1): Constant time, independent of input size (e.g., accessing an array element
by index).
• O(log n): Logarithmic time, runtime grows slowly with input size (e.g.,
binary search).
• O(n): Linear time, runtime grows proportionally to input size (e.g., traversing a
linked list).
• O(n log n): Linearithmic time, common in efficient sorting algorithms (e.g.,
merge sort).
• O(n^2): Quadratic time, runtime grows with the square of the input size (e.g.,
bubble sort).
• O(2^n): Exponential time, very slow and impractical for large inputs (e.g.,
some brute-force algorithms).
------------------------------xx-------------------------
Big O Notation Order of Complexity (Ascending)
1. O(1) Constant Time: The execution time or space requirement remains constant
regardless of the input size.
2. O(log n) Logarithmic Time: The execution time or space requirement grows logarithmically
with the input size.
3. O(n) Linear Time: The execution time or space requirement grows linearly with the input
size.
4. O(n log n) Log-linear (Quasilinear) Time: The execution time or space requirement grows
proportionally to n times the logarithm of n.
5. O(n²) Quadratic Time: The execution time or space requirement grows quadratically with
the input size.
6. O(2ⁿ) Exponential Time: The execution time or space requirement grows exponentially
with the input size.
7. O(n!) Factorial Time: The execution time or space requirement grows factorially with the
input size.
