ADVANCED DATA

STRUCTURE AND
ALGORITHM
UNIT-I
 Algorithm
• What is algorithm?
• “A process or set of rules to be followed in calculations or other problem-
solving operations”.
• Algorithm refers to a set of rules/instructions that step-by-step define how a
work is to be executed upon in order to get the expected results.
• Search − Algorithm to search an item in a data structure.
• Sort − Algorithm to sort items in a certain order.
• Insert − Algorithm to insert item in a data structure.
• Update − Algorithm to update an existing item in a data structure.
• Delete − Algorithm to delete an existing item from a data structure.
 How to Write an Algorithm?
• There are no well-defined standards for writing algorithms. Rather, it
is problem and resource dependent.
• Ex: Problem − Design an algorithm to add two numbers and display the result.

Step 1 − START Step 1 − START ADD

Step 2 − declare three integers a, Step 2 − get values of a
b&c &b
Step 3 − define values of a & b Step 3−c←a+b
Step 4 − add values of a & b Step 4 − display c
Step 5 − store output of step 4 to Step 5 − STOP
c
Step 6 − print c
Step 7 − STOP
 Algorithm as a technology
• If computers were indefinitely fast, any available approach to a
problem's solution would be sufficient.
• Both memory space and computing time are finite resources.
• Algorithms that are efficient in terms of time or space will aid you in
making sensible use of these resources.
• The insertion sort, time as c1n2,
• where c1 is a constant that is independent of n. That is, the duration is roughly inversely
proportional to n2.
• Merge sort, time as c2nlog2 n,
• where log n is short for log2 n and c2 is yet another constant that is independent of n.
• Insertion sort has a smaller constant factor than merge sort, causing c1
to be greater than c2.
Cont.…
 Algorithm Analysis
• Two different stages:
• A Priori Analysis − Efficiency of an algorithm is measured by assuming that all
other factors, for example, processor speed, are constant and have no effect
on the implementation.
• A Posterior Analysis − This is then executed on target computer machine. In
this analysis, actual statistics like running time and space required, are
collected.
• Algorithm analysis deals with the execution or running time of various
operations involved.
• The running time of an operation can be defined as the number of
computer instructions executed per operation.
 Time and space complexity of an
algorithm
• Two main factors
• Time Factor − Time is measured by counting the number of key operations
such as comparisons in the sorting algorithm.
• Space Factor − Space is measured by counting the maximum memory space
required by the algorithm.
• The complexity of an algorithm f(n) gives the running time and/or the
storage space required by the algorithm in terms of n as the size of
input data.
 Space Complexity
• It represents the amount of memory space
• Two components:
• A fixed part that is a space required to store certain data and variables, that
are independent of the size of the problem.
• Ex: Constant
• A variable part is a space required by variables, whose size depends on the
size of the problem.
• Ex: Dynamic memory allocation, Recursion stack space.
 Time Complexity
• Amount of time required by the algorithm to run to completion.
• Time requirements can be defined as a numerical function T(n).
• T(n) can be measured as the number of steps, provided each step
consumes constant time.
• Ex: Addition of two n-bit integers takes n steps.
• Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for
the addition of two bits.
• Here, we observe that T(n) grows linearly as the input size increases.
 Asymptotic analysis
• Its refers to computing the running time of any operation in
mathematical units of computation.
• The running time of one operation is computed as f(n) and may be for
another operation it is computed as g(n2).
• This means the first operation running time will increase linearly with the
increase in n and the running time of the second operation will increase
exponentially when n increases.
• The time required by an algorithm falls under three types
• Best Case − Minimum time required for program execution.
• Average Case − Average time required for program execution.
• Worst Case − Maximum time required for program execution.
 Asymptotic Notation
• Commonly used asymptotic notations
• Ο − Big Oh Notation
• Ω − Big Omega Notation
• Θ − Theta Notation
• o − Little Oh Notation
• ω − Little Omega Notation
 Ο − Big Oh Notation
• The notation Ο(n) is the formal way to express the upper bound of an
algorithm's running time.
• It measures the worst case time complexity or the longest amount of
time an algorithm can possibly take to complete.
• O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

Example
Let us consider a given function, f(n) =
4.n3+10.n2+5.n+1.
Considering g(n) = n3
f(n) ≥ 5.g(n) for all the values of n > 2.
Hence, the complexity of f(n) can be represented
as O (g (n) ) ,i.e. O (n3).
 Ω − Big Omega Notation
• The notation Ω(n) is the formal way to express the lower bound of an
algorithm's running time.
• It measures the best case time complexity or the best amount of
time an algorithm can possibly take to complete.
• Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥
n0 }
Example
Let us consider a given function, f(n) =
4.n3+10.n2+5.n+1
Considering g(n) = n3 , f(n) ≥ 4.g(n) for all the values
of n > 0.
Hence, the complexity of f(n) can be represented
as Ω (g (n) ) ,i.e. Ω (n3).
 Θ − Theta Notation
• Express both the lower bound and the upper bound of an algorithm's
running time.
• Some may confuse the theta notation as the average case time
complexity, while big theta notation could be almost accurately used
to describe the average case
• Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤
c2 * g(n) for all n ≥ n0}

Let us consider a given function, f(n) =

4.n3+10.n2+5.n+1
Considering g(n) = n3 , 4.g(n)≤ f(n)≤ 5.g(n) for all
the values of n.
Hence, the complexity of f(n) can be represented
as Ɵ (g (n) ) ,i.e. Ɵ (n3).
 Little Oh (o) and Little Omega (ω)
Notations
• The Little Oh and Little Omega notations also represent the best and
worst case complexities but they are not asymptotically tight in
contrast to the Big Oh and Big Omega Notations.
• Therefore, the most commonly used notations to represent time
complexities are Big Oh and Big Omega Notations only.
 Importance of efficient algorithm
• Understanding Algorithm Efficiency
• Algorithm efficiency refers to the ability of an algorithm to effectively utilize computational
resources, such as time and memory, to solve a given problem.
• Importance of Algorithm Efficiency
• Faster Execution
• Reduce execution time, enable quicker result.
• Scalability
• Efficient algorithms can handle larger datasets without causing a significant increase in execution time
or memory usage.
• Resource Utilization
• By optimizing time and space complexity, you can minimize the need for expensive hardware upgrades
or cloud computing resources
• Better User Experience
• Faster response times, smoother interactions, and seamless data processing contribute .
Program performance Measurement
• When there are multiple alternative algorithms to solve a problem,
we analyze them and pick the one which is best suitable for our
requirements.
• Generally, the performance of an algorithm depends on the following
elements...
• Whether that algorithm is providing the exact solution for the problem?
• Whether it is easy to understand?
• Whether it is easy to implement?
• How much space (memory) it requires to solve the problem?
• How much time it takes to solve the problem? Etc.,
 Recurrence
• Some computer programming languages allow a module or function to
call itself. This technique is known as recursion.
• In recursion, a function α either calls itself directly or calls a
function β that in turn calls the original function α.
• The function α is called recursive function.
• A recurrence is an equation or inequality that describes a function in
terms of its values on smaller inputs.
• For Example, the Worst Case Running Time T(n) of the MERGE
SORT Procedures is described by the recurrence
• T (n) = θ (1) if n=1
• 2T (n/2) + θ (n) if n>1
Recurrence Properties
• A recursive function can go infinite like a loop. To avoid infinite
running of recursive function, there are two properties that a
recursive function must have
• Base criteria − There must be at least one base criteria or condition, such
that, when this condition is met the function stops calling itself recursively.
• Progressive approach − The recursive calls should progress in such a way that
each time a recursive call is made it comes closer to the base criteria.
 Recurrence methods
• Here are four methods for solving Recurrence:
• Substitution Method
• Iteration Method
• Recursion Tree Method
• Master Method
Substitution Method