Chapter-One
Fundamentals of Data structure and algorithm
Outline
Introduction to Data structure and algorithms
Algorithms
Complexity of an algorithms
Asymptotic Notation
Conclusion
1
Introduction to Data Structures and Algorithms
How to solve a problem
Given a problem, the first step to solve the problem is obtaining one’s
own abstract view, or model, of the problem. This process of
modeling is called abstraction.
2
Abstraction
•The model defines an abstract view to the problem.
•This implies that the model focuses only on problem related and that
a programmer tries to define the properties of the problem.
These properties include
The data which are affected and
The operations that are involved in the problem.
With abstraction you create a well-defined entity that can be properly
handled. These entities define the data structure of the program.
3
Data Structures and Algorithms
Program- A program is written in order to solve a problem.
A solution to a problem actually consists of two things:
A way to organize the data
Sequence of steps to solve the problem
The way of organizing data in computers memory is said to be Data
Structure and the sequence of computational steps to solve a problem
is said to be an algorithm.
Therefore, a program is nothing but data structures plus algorithms.
Data Structure is a way of collecting and organizing data in such a
way that we can perform operations on these data in an effective way.
Data Structures is about rendering data elements in terms of some
relationship, for better organization and storage.
For example, we have some data which has, player's name "Virat" and age 26.
Here "Virat" is of String data type and 26 is of integer data type. We can
organize this data as a record like Player record, which will have both player's
name and age in it. Now we can collect and store player's records in a file or
database as a data structure.
For example: "Dhoni" 30, "Gambhir" 31, "Sehwag" 33
Basic types of Data Structures
As we have discussed above, anything that can store data can be called
as a data structure, hence Integer, Float, Boolean, Char etc, all are data
structures. They are known as Primitive Data Structures /Built in
data structure.
Then we also have some complex Data Structures, which are used to
store large and connected data. This data structures are called Abstract
Data Structures /User defined data structures .
Some example of Abstract Data Structure are :
Linked List
Tree
Graph
Stack, Queue etc.
Data structures types.
What is an Algorithm?
An algorithm is a finite set of instructions or logic, written in order, to
accomplish a certain predefined task.
Algorithm is not the complete code or program, it is just the core
logic(solution) of a problem, which can be expressed either as an
informal high-level description as pseudocode or using a flowchart.
• Example
Properties of an algorithm
Finiteness: Algorithm must complete after a finite number of steps
Definiteness: Each step must be clearly defined, having one and only one
interpretation.
Sequence: Each step must have a unique defined preceding and succeeding
step.
Feasibility: It must be possible to perform each instruction
Correctness: It must compute correct answer for all possible legal inputs.
Language Independence: It must not depend on any one programming
language.
Completeness: It must solve the problem completely.
Properties of an algorithm
Effectiveness: It must be possible to perform each step exactly and in a
finite amount of time.
Efficiency: It must solve with the least amount of computational
resources such as time and space.
Generality: Algorithm should be valid on all possible inputs.
Input/Output: There must be a specified number of input values, and
one or more result values
An algorithm is said to be efficient and fast, if it takes less time to
execute and consumes less memory space.
The performance of an algorithm is measured on the basis of
following properties:
Time Complexity
Space Complexity
Space Vs Time Complexity
Space Complexity:
When we design an algorithm to solve a problem,
it needs some computer memory to complete its execution.
For any algorithm, memory is required.
Total amount of computer memory required by an algorithm to complete
its execution is called as space complexity of that algorithm.
Its the amount of memory space required by the algorithm, during
the course of its execution.
A measure of the amount of working storage an algorithm needs.
Space complexity must be taken seriously in situations where
limited memory is available.
13
Space Complexity(cont…)
An algorithm generally requires space for following components :-
Instruction Space: It is the space required to store the executable
version of the program.
It is the amount of memory used to store compiled version of
instructions.
This space is fixed, but varies depending upon the number of lines of
code in the program.
Data Space: It is the space required to store all the constants and
variables(including temporary variables) value.
Environment Space: It is the amount of memory used to store
information of partially executed functions at the time of function call.
14
Time Complexity
Time Complexity is a way to represent the amount of time required by
the program to run till its completion.
It's generally a good practice to try to keep the time required
minimum, so that our algorithm completes it's execution in the
minimum time possible.
Designing an algorithm which requires minimum time complexity
were recommended for algorithm developers
Example:- It takes one nano second, can execute with in one minute etc.
15
Calculating the Space Complexity
For calculating the space complexity, we need to know the value of memory used
by different type of datatype variables, which generally varies for different
operating systems, but the method for calculating the space complexity remains
the same.
Ex(32 bits):-
2 bytes to store Integer value.
4 bytes to store Floating Point value.
1 byte to store Character value.
2 bytes of memory for return value.
16
Calculating the Space Complexity
• Example:-
In the above piece of code,
it requires 2 bytes of memory to store variable 'a' and another 2 bytes of memory is
used for return value.
Note:-That means, totally it requires 4 bytes of memory to complete its execution.
17
Question-1:- Calculate the space complexity of the following
instruction/code.
18
Answer of Question-1
In the above piece of code it requires,
'n*2' bytes of memory to store array variable 'a[ ]’,
2 bytes of memory for integer parameter ’n’,
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes
each), and
2 bytes of memory for return value.
That means, totally it requires '2n+8' bytes of memory to complete
its execution.
Here, the total amount of memory required depends on the value of 'n’.
As 'n' value increases the space required also increases proportionately.
19
Time Complexity
Time Complexity is a way to represent the amount of time required by
the program to run till its completion.
It's generally a good practice to try to keep the time required
minimum, so that our algorithm completes it's execution in the
minimum time possible.
Designing an algorithm which requires minimum time complexity
were recommended for algorithm developers
Example:- It takes one nano second, can execute with in one minute etc.
20
Time Complexity(Cont…)
Generally, the running time of an algorithm depends upon the
following...
Whether it is running on Single processor machine or Multi processor
machine.
Whether it is a 32 bit machine or 64 bit machine.
Read and Write speed of the machine.
The amount of time required by an algorithm to
perform Arithmetic operations, logical operations, return value
and assignment operations etc.,
Input data
21
Time Complexity(Count…)
To calculate the time complexity of an algorithm, we need to define a
model machine.
Note:- Let us assume a machine with following configuration...
It is a Single processor machine
It is a 32 bit Operating System machine
It performs sequential execution
It requires 1 unit of time for Arithmetic and Logical operations
It requires 1 unit of time for Assignment and Return value
It requires 1 unit of time for Read and Write operations
22
• Now we can calculate the time complexity of following example code
by using the above-defined model machine...
• Example:-
23
Time complexity(cont.….)
In the above sample code,
it requires 1 unit of time to calculate a+b , and
1 unit of time to return the value.
That means, totally it takes 2 units of time to complete its execution.
And it does not change based on the input values of a and b.
That means for all input values, it requires the same amount of time
i.e. 2 units.
24
Asymptotic Notations
What is Asymptotic Notation?
Whenever we want to perform analysis of an algorithm, we need to
calculate the complexity of that algorithm /time & space/.
But when we calculate the complexity of an algorithm it does not
provide the exact amount of resource required.
So instead of taking the exact amount of resource, we represent that
complexity in a general form (Notation) which produces the basic
nature of that algorithm.
We use that general form (Notation) for analysis process.
Note:-Asymptotic notation of an algorithm is a mathematical
representation of its complexity.
25
Asymptotic Notations
In asymptotic notation,
when we want to represent the complexity of an algorithm, we use only the
most significant terms in the complexity of that algorithm and ignore least
significant terms in the complexity of that algorithm.
Example:-Consider the following time complexities of two algorithms...
• Algorithm 1 : 5n2 + 2n + 1
• Algorithm 2 : 10n2 + 8n + 3
In above two time complexities,
For larger value of 'n' the term '2n + 1' in algorithm 1 has least
significance than the term '5n2', and
The term '8n + 3' in algorithm 2 has least significance than the term '10n2'.
26
Asymptotic Notations
Here, for larger value of 'n' the value of most significant terms
( 5n2 and 10n2 ) is very larger than the value of least significant terms
( 2n + 1 and 8n + 3 ).
So for larger value of 'n' we ignore the least significant terms to
represent overall time required by an algorithm.
In asymptotic notation, we use only the most significant terms to
represent the complexity of an algorithm.
27
Types of Asymptotic Notations
We use three types of asymptotic notations to represent the growth of
any algorithm, as input increases:
i. Big Theta (Θ)
ii. Big Oh(O)
iii. Big Omega (Ω
28
Big Theta (Θ) Notation
the Big-Θ / Big Theta/ notation is like the average value or range
within which the actual time of execution of the algorithm will be.
For example, assume if time complexity of an algorithm is
represented by the expression 3n2 + 5n, and
we use the Big-Θ notation to represent this,
then the time complexity would be Θ(n2), ignoring the constant
coefficient and removing the insignificant part, which is 5n.
29
Big Oh(O)
This notation is known as the upper bound of the algorithm, or a
Worst Case of an algorithm
This notation is known as the upper bound of the algorithm, or a
Worst Case of an algorithm.
Example:- Consider Linear Search algorithm, in which we traverse an
array elements, one by one to search a given number
Using this notation n /worst case/
30
Big Omega (Ω)
Big Omega notation is used to define the lower bound of any algorithm
or we can say the best case of any algorithm.
This always indicates the minimum time required for any algorithm for
all input values, therefore the best case of any algorithm.
In simple words, when we represent a time complexity for any algorithm
in the form of big-Ω, we mean that the algorithm will take at least this
much time to complete it's execution.
It can definitely take more time than this too.
31
Reading Assignment
Read for the following concepts
Applications of data structure and algorithms
Asymptotic notation in detail
Compare and contrast Littlie-o Notation vs Littlie-Omega notation
32
See You Next!!
33
