Chapter One

Data Structure and Algorithm Analysis

By Maaza
2017E.C
 Data Structures and Algorithms
• A program
• A set of instruction which 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 data are organized in a computers memory is said
to be Data Structure. The sequence of computational steps
to solve a problem is said to be an Algorithm.
• Therefore, a program is Data structures plus Algorithm.
 Con…
• Data structures are used to model the world or part of
the world. How?
 The value held by a data structure represents some specific
characteristic of the world.
 The characteristic being modeled restricts the possible
values held by a data structure and the operations to be
performed on the data structure.
• The first step to solve the problem is obtaining ones own
abstract view, or model, of the problem.
• This process of modeling is called abstraction. The
model defines an abstract view to the problem. The
model should only focus on problem related stuff.
 Con…
• Abstraction
 Abstraction is a process of classifying characteristics as relevant and
irrelevant for the particular purpose at hand and ignoring the
irrelevant ones.
• Example: model students of SU.
• Relevant:
Char Name[15];
Char ID[11];
Char Dept[20];
int Age, year;
• Non relevant:
float hieght, weight;
 Con…
• Using the model above, 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
An entity with the properties just described is
called an abstract data type (ADT).
 Abstract Data Types
• Abstract Data Types Consists of data to be stored
and operations supported on them. Abstract Data
Types is a specification that describes a data set
and the operation on that data.
• The ADT specifies:
What data is stored.
What operations can be done on the data. However, it
does not specify how to store or how to implement
the operation. It is also independent of any
programming language.
 Con…
• Example:
• ADT employees of an organization:
This ADT stores employees with their relevant
attributes and discarding irrelevant attributes.
Relevant:- Name, ID, Sex, Age, Salary, Dept, Address
Non Relevant :- weight, color, height
• This ADT supports hiring, firing, retiring,
… operations.
 Con…
• Data Structure
 In Contrast a data structure is a language construct that the
programmer has defined in order to implement an abstract
data type.
• What is the purpose of data structures in programs?
 Data structures are used to model a problem.
• Example:
struct Student_Record
{
char name[20];
char ID_NO[10];
char Department[10];
int age;
};
 Con…
• Attributes of each variable:
Name: Textual label.
Address: Location in memory.
Scope: Visibility in statements of a program.
Type: Set of values that can be stored + set of
operations that can be performed.
Size: The amount of storage required to represent
the variable.
Life time: The time interval during execution of a
program while the variable exists.
 Algorithms
• Algorithm Is a concise specification of an operation
for solving a problem.
• Algorithm is a well-defined computational
procedure that takes some value or a set of values
as input and produces some value or a set of values
as output:
• Inputs ==> Algorithm ==> Outputs
 Con…
• An algorithm is a specification of a behavioral process.
• It consists of a finite set of instructions that govern
behavior step-by-step.
• It is part of what constitutes a data structure. Data
structures model the static part of the world. They are
unchanging while the world is changing.
• In order to model the dynamic part of the world we
need to work with algorithms.
• Algorithms are the dynamic part of a program’s world
model.
• An algorithm transforms data structures from one state
to another state.
 Con…
• What is the purpose of algorithms in programs?
• Take values as input:
Example: cin>>age;
• Change the values held by data structures:
Example: age=age+1;
• Change the organization of the data structure:
Example: Sort students by name
• Produce outputs:
Example: Display student’s information
 Con…
• The quality of a data structure is related to its ability to
successfully model the characteristics of the world
(problem).
• Similarly, the quality of an algorithm is related to its
ability to successfully simulate the changes in the world.
• However, the quality of data structure and algorithms is
determined by their ability to work together well.
• Generally speaking, correct data structures lead to
simple and efficient algorithms.
• And correct algorithms lead to accurate and efficient
data structures.
 Properties of Algorithms
Finiteness: Algorithm must complete after a finite
number of steps. Algorithm should have a finite number
of steps.
Definiteness (Absence of ambiguity): Each step must be
clearly defined, having one and only one interpretation.
At each point in computation, one should be able to tell
exactly what happens next.
Sequential: Each step must have a uniquely defined
preceding and succeeding step. The first step (start step)
and last step (halt step) must be clearly noted.
Feasibility: It must be possible to perform each
instruction. Each instruction should have possibility to
be executed.
 Con…
 Correctness: It must compute correct answer for all possible legal
inputs. The output should be as expected and required and correct.
 Language Independence: It must not depend on any one
programming language.
 Completeness: It must solve the problem completely.
 Effectiveness: Doing the right thing. It should yield the correct result
all the time for all of the possible cases.
 Efficiency: It must solve with the least amount of computational
resources such as time and space. Producing an output as per the
requirement within the given resources (constraints).
 Input/output: There must be a specified number of input values, and
one or more result values. Zero or more inputs and one or more
outputs.
 Precision: The result should always be the same if the algorithm is
given identical input.
 Con…
 Simplicity: A good general rule is that each step should
carry out one logical step. What is simple to one processor
may not be simple to another.
• Levels of abstraction: Used to organize the ideas
expressed in algorithms.
• It is also used to hide the details of a given activity and
refer to just a name for those details. The simple
(detailed) instructions are hidden inside modules.
• Well-designed algorithms are organized in terms of
levels of abstraction.
 Con…
• Why to Learn Data Structures & Algorithms (DSA)?
 As applications are getting complex and data rich, there are
three common problems that applications face now-a-days.
 Data Search, Processor speed, Multiple requests
 DSA are used in virtually every software system, from operating
systems to web applications:
 For managing large amounts of data, scheduling tasks, planning
routes, solving complex problems
• What is The Difference Between Data Type and Data
Structure?
 Algorithm analysis
• Algorithm analysis refers to the process of determining
how much computing time and storage that algorithms
will require. In other words, it’s a process of predicting
the resource requirement of algorithms in a given
environment.
• In order to solve a problem, there are many possible
algorithms.
• One has to be able to choose the best algorithm for the
problem at hand using some scientific method.
• To classify some data structures and algorithms as
good, we need precise ways of analyzing them in terms
of resource requirement.
 Con…
• The main resources are:
Running Time
Memory Usage
Communication Bandwidth
• Note: Running time is the most important since
computational time is the most precious resource
in most problem domains.
• There are two approaches to measure the
efficiency of algorithms:
 Empirical approaches
 Theoretical approaches
 Empirical Algorithm Analysis
• It works based on the total running time of the program. It
uses actual system clock time.
• Example:
t1(Initial time before the program starts)
for(int i=0; i<=10; i++)
cout<<i;
t2 (final time after the execution of the program is finished)
• Running time taken by the above algorithm (TotalTime) =
t2-t1;
• It is difficult to determine efficiency of algorithms using this
approach, because clock-time can vary based on many
factors.
• For example:
 Con…
a) Processor speed of the computer
 1.78GHz ==> 10s
 2.12GHz ==> 15s
b) Current processor load
 Only the work 10s
 With printing 15s With printing &
 browsing the internet >15s
c) Specific data for a particular run of the program
Input size
Input properties
T1
for(int i=0; i<=n; i++)
cout<<i;
T2
T=t2-t1;
For n=100, T>=0.5s
n=1000, T>0.5s d)
• Operating System
 Multitasking Vs Single tasking
 Internal structure
 Theoretical Algorithm Analysis
• Determining the quantity of resources required using
mathematical concept.
• Analyze an algorithm according to the number of basic
operations (time units) required, rather than according
to an absolute amount of time involved.
• We use theoretical approach to determine the
efficiency of algorithm because:
 The number of operation will not vary under different
conditions.
 It helps us to have a meaningful measure that permits
comparison of algorithms independent of operating
platform.
 It helps to determine the complexity of algorithm.
 Con…
• Complexity Analysis
• Complexity Analysis is the systematic study of
the cost of computation, measured either in:
Time units
Operations performed, or
The amount of storage space required.
• Two important ways to characterize the
effectiveness of an algorithm are its Space
Complexity and Time Complexity.
 Con…
• Time Complexity: Determine the approximate amount of
time (number of operations) required to solve a problem
of size n.
 The limiting behavior of time complexity as size increases is
called the Asymptotic Time Complexity.
• Space Complexity: Determine the approximate memory
required to solve a problem of size n.
 The limiting behavior of space complexity as size increases is
called the Asymptotic Space Complexity.
• Asymptotic Complexity of an algorithm determines the
size of problems that can be solved by the algorithm.
 Con…
• Factors affecting the running time of a program:
 CPU type (80286, 80386, 80486, Pentium I---IV)
 Memory used
 Computer used
 Programming Language C (fastest), C++ (faster), Java (fast) C is
relatively faster than Java, because C is relatively nearer to
Machine language, so, Java takes relatively larger amount of
time for interpreting/translation to machine code.
 Algorithm used
 Input size
 Note: Important factors for this course are Input size and
Algorithm used.
• Complexity analysis involves two distinct phases:
 Algorithm Analysis
 Order of Magnitude Analysis
 Algorithm Analysis
• Algorithm Analysis: Analysis of the algorithm or data
structure to produce a function T(n) that describes the
algorithm in terms of the operations performed in
order to measure the complexity of the algorithm.
• Order of Magnitude Analysis: Analysis of the function
T (n) to determine the general complexity category to
which it belongs.
• There is no generally accepted set of rules for
algorithm analysis. However, an exact count of
operations is commonly used.
• To count the number of operations we can use the
following Analysis Rule.
 Con…
• Analysis Rules:
1. Assume an arbitrary time unit.
2. Execution of one of the following operations takes
time 1 unit:
 Assignment Operation Example: i=0;
 Single Input/Output Operation Example: cin>>a;
cout<<“hello”;
 Single Boolean Operations Example: i>=10
 Single Arithmetic Operations Example: a+b;
 Function Return Example: return sum;
3. Running time of a selection statement (if, switch) is
the time for the condition evaluation plus the
maximum of the running times for the individual
clauses in the selection.
 Con…
• Examples: 2)
1)

3)
 Con…
4) 5)

6)
 Formal Approach to Analysis
• In the above examples we have seen that analyzing Loop
statements is so complex. It can be simplified by using some
formal approach in which case we can ignore initializations,
loop controls, and updates.
• Simple Loops: Formally, for loop can be translated to a
summation. The index and bounds of the summation are the
same as the index and bounds of the for loop.
 Suppose we count the number of additions that are done. There is 1
addition per iteration of the loop, hence n additions in total.
 Con…
• Nested Loops: Formally, nested for loops translate into
multiple summations, one for each For loop.

Consecutive Statements: Formally, add the running times of the

separate blocks of your code.
 Con…
• Conditionals: (Formally take maximum) Example:
 Con…
• Recursive: Formally -Usually difficult to analyze.
• Example: Factorial
 Categories of Algorithm Analysis
• Algorithms may be examined under different situations
to correctly determine their efficiency for accurate
comparison.
• Best Case Analysis
 Best case analysis assumes the input data are arranged in
the most advantageous order for the algorithm.
 It also takes the smallest possible set of inputs and causes
execution of the fewest number of statements. Moreover,
it computes the lower bound of T(n), where T(n) is the
complexity function.
• Examples: For sorting algorithm
 If the list is already sorted (data are arranged in the required
order).
 For searching algorithm If the desired item is located at first
accessed position.
 Con…
• Worst Case Analysis:
 Worst case analysis assumes the input data are arranged in the
most disadvantageous order for the algorithm.
 Takes the worst possible set of inputs. Causes execution of the
largest number of statements. Computes the upper bound of
T(n) where T(n) is the complexity function.
• Example:
While sorting, if the list is in opposite order.
While searching, if the desired item is located at
the last position or is missing.
 Con…
• Examples:
 For sorting algorithms, If the list is in opposite order.
 For searching algorithms, If the desired item is located at the last
position or is missing.
• Worst case analysis is the most common analysis because, it
provides the upper bound for all input (even for bad ones).
• Average case analysis is often difficult to determine and
define. If situations are in their best case, no need to develop
algorithms because data arrangements are in the best
situation.
• Best case analysis can not be used to estimate complexity.
• We are interested in the worst case time since it provides a
bound for all input-this is called the “Big-Oh” estimate.
 Con…
• Average Case Analysis
 Determine the average of the running time overall
permutation of input data. Takes an average set of inputs.
 It also assumes random input size. It causes average
number of executions.
 Computes the optimal bound of T(n) where T(n) is the
complexity function.
 Sometimes average cases are as bad as worst cases and as
good as best cases.
• Examples:
 For sorting algorithms, While sorting, considering any
arrangement (order of input data).
 For searching algorithms While searching, if the desired
item is located at any location or is missing.
 Order of Magnitude
• Order of Magnitude refers to the rate at which the storage or time
grows as a function of problem size.
 This type of analysis is called Asymptotic analysis.
• Asymptotic analysis refers to computing the running time of any
operation in mathematical units of computation.
• Asymptotic Notations: Execution time of an algorithm depends on
the instruction set, processor speed, disk I/O speed, etc.
 Hence, we estimate the efficiency of an algorithm asymptotically.
 Time function of an algorithm is represented by T(n), where n is the
input size.
• Different types of asymptotic notations are used to represent the
complexity of an algorithm.
 Big Oh Notation(O ),
 Big omega Notation(Ω), Big theta Notation(θ), Little Oh Notation(o ),
Little omega Notation(ω )(Reading Assignment)
 Big Oh Notation(O)
• The notation Ο(n) is the formal way to express the upper bound
of an algorithm's running time. is the most commonly used
notation.
• It measures the worst case time complexity or the longest
amount of time an algorithm can possibly take to complete.
• A function f(n) can be represented is the order of g(n) that
is O(g(n)), if there exists a value of positive integer n as n0 and a
positive constant c such that − f(n)⩽c.g(n), for n>n0 in all case
• Hence, function g(n) is an upper bound for function f(n),
as g(n) grows faster than f(n).
 Con…
• Rules to estimate Big Oh of a given function
• Pick the highest order. Ignore the coefficient.
• Example: T(n)=3n + 5 ==> O(n)
 T(n)=3n2+4n+2 ==> O(n2)
• Some known functions encountered when analyzing
algorithms. (Complexity category for Big-Oh).
 Rule 1: If T1(n)=O(f(n)) and T2(n)=O(g(n)), then
T1(n)+T2(n)=max(O(f(n)),O(g(n))), T1(n)*T2(n)=O(f(n)*g(n))
 Rule 2: If T(n) is a polynomial of degree k, then T(n)=θ(nk).
 Rule 3: logk n=O(n) for any constant k. This tells us that
logarithms grow very slowly.
 Con…
• The order of the body statements of a given algorithm is very
important in determining Big-Oh of the algorithm.
• Example: Find Big-Oh of the following algorithm.

1) 2)