0% found this document useful (0 votes)
57 viewsUnit 4
DSA Notes
Uploaded by
Sayan HalderCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
57 viewsUnit 4
DSA Notes
Uploaded by
Sayan HalderCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 26
~@ Onit- ;
: . i
. Cudavsaranp, BMSTT, blas
Chapter 1. Introduction
LI Need for studying algorithms: The study of algorithms is the cornerstone of computer
science It can be recognized as the core of computer science, Computer programs would
not exist without algorithms. With computers becoming an essential part of our profes-
sional & personal life's, studying algorithms becomes a necessity, more so for computer
science engineers
Another reason for studying algorithms is that if we know a standard set of important
algorithms ,They further our analytical skills & help us in developing new algorithms for
Tequired applications
1.2 ALGORITHM
a particular task. In
An algorithm is finite set of instructions that is followed, accomplishes
addition, all algorithms must satisfy the following criteria:
1. Input. Zero or more quantities are externally supplied. _
2. Output. At least one quantity is produced.
3. Definiteness. Each instruction is clear and produced.
4. Finiteness. If we trace out the instruction of an algorithm, then for all cases, the algo-
rithm terminates after a finite number of steps.
5. Effectiveness. Every instruction must be very basic so that it can be carried out, in
principal, by a person using only pencil and paper. It is not enough that each operation
be definite as in criterion 3; it also must be feasible,
po sapien a Beans quam b iquonsi WsTECE I
4° pabom ie: for oLtesvig a donuinus O
5 Ben wd g me:
fer ony agihmt iinpat iM 4 Gif ae’
cheatProblem
Algorithm
| conmure = output
Fig 1a.
An algorithm is composed of a finite set of steps, each of which may require one or more Op-
erations. The possibility of a computer cans ying out these operations necessitates that certain
constraints be placed on the type of opérations an algorithm can include. The fourth criterion
for algorithms we assume in this book is that they terminate after a finite number of opera-
tions.
Criterion 5 requires that each operation be effective: each step must be such that it can, at least
in principal, be done by a person using pencil and paper in a finite amount of time. Performing
arithmetic on integers is an example of effective operation, but arithmetic with real numbers is
not, since some values may be expressible only by infinitely long decimal expansion. Adding
‘two such numbers would violet the effectiveness property.
Algorithms that are definite and effective are also called computational procedures.
© The same algorithm can be represented in same algorithm can.be represented in sever-
al ways
* Several algonthms to solve the same problem
« Different ideas different speed
Example:Another way of representation of the same algorithm
Problem:GCD of Two numbers mn
Function Euckd(aig
Input specifiastion Ty
‘© NUS .Nonne ive.not both zerq
Euclids algorithm tf b =o Nhl &
gcd(m.n)=gcdin,m mod n) return (Cuetet C19 rods),
Untill m mod n =0,since gedim,0) =m Ord Eucted
Euclids algorithm
Stepl:if n=0 return val of m & stop else proceed step
Step 2:1
Step 3:
Another algorithm to solve the same problem
Euclids algorithm
Step1:Assign the value of min(m,n) to t
Step 2:1
Step 3: Divide n by tif the remainder is 0,return the value of t as the answer and
ivide m by tif remainder is 0,g0 to step3 else goto step4
stop, otherwise proceed to step4
Step4 :Decrease the value of t by 1. go to step 2
1.3 Fundamentals of Algorithmic problem solving. __-kis
" a
Understanding the problem [ardent Prete)
Ascertain the capabilities of the computational device
Exact /approximate soln.
Com putstions means
Decide on the appropriate data structure
areaninse
Algorithm design techniques
Methods of specifying an algorithm
Proving an algorithms correctness
‘Analysing an algorithmsn should be understood complete
lem give
ne the problem The Ambien if a Known algorithm ex
problems &
Understan
ly.Check if it is similar to some standard
hart which
ists otherwise a new algorithny has to he devised Creating an agorithin ae
may never be fully automated, Am important step_ nthe desizn 8 6 SPECT
stance of the problem, 1 onders
Ascertain the capabilities of the computational device: Onee a problem 1 *
tood we need to Know the capabilities of the computing device this can be done by
ailability,
Knowing the type of the architecture,speed & memory
Exact /approximate soln.: Once algorithm is devised, it is necessary to show that it
computes answer for all the possible legal inputs, The solution is stated in two
forms,Exact solution or approximate solution.examples of problems where an exact
solution cannot be obtained are i)Finding a squareroot of number.
{i)Solutions of non linear equations.
:Some algorithms do not demand any in
Decide on the appropriate data struct
genuity in representing their inputs.Someothers are in fact are predicted on ingenious
data structures.A data type is a well-defined collection of data with a well-defined set
~ of operations on it.A data structure is an actual implementation of a particular abstract
data type. The Elementary Data Structures are
ArraysThese let you access lots of data fast. (good) .You can have arrays of any other da
ta type. (good) -However, you cannot make arrays bigger if your program decides it needs
more space. (bad)
RecordsThese let you organize non-homogeneous data into logical packages to keep every-
thing together. (good) These packages do not include operations, just data fields (bad, which
is why we need objects) Records do not help you process distinct items in loops (bad, which
is why arrays of records are used)
SetsThese let you represent subsets of a set with such operations as intersection, union, and
equivalence. (good) .Built-in sets are limited (o a certain small size. (bad, but we can build our
‘own set data type out of arrays to solve this problem if necessary)Algorithm design techniques, Creating an algorithm is
tomated. By
rategies, it wi
Mastering these design st
useful
iN bece
algorithms. Dynan,
Peci
ally useful in fie
" computer science such
MPortant design techniques are Hine
PE AN algorithm: There
are m:
langu:
nthm: use of natural
ABE OT pseudocode & Floweharts
A Pseudo code is a mixture of natur, z
flowchart is a method of “XPressing an algorithm by a collection
shapes.
Analyzing algorithms: As an algorithm is executed,
uses the computers central processing
nit to perform ‘ory (both immediate and auxiliary) to hold the program
form operation and its memory (both i iliary) to pro; ;
i data. Analysis of erformance analysis refers to the task of determining
lysis of algorithms and perf f
. Analysis
}ow much computing time and storage an algorithm requires. This is a challenging area in
ig time at i Ig res. This iallenging.
h
hich some times req) rate mathematical skill. An important result of this study is that i
re grate m: sh sult of
S require a
imi
er another.
‘alue of one algorithm over an
ke quantitative judgments about the value of one alg
lake
allows you to miAnother result is that it allows you to predict whether the software will meet any efficiency -
constraint that exits
Performance analysis
‘There are any criteria upon which we can judge an algorithm for instance:
1, Does it do what we want to do?
2. Does it work correctly according to the original specifications to the task?
3-is there documentation that describes how to use it and how it works?
4. Are procedures created in such a way that they perform logical sub functions?
5. is the code readable?
The space complexity of an algorithm is the amount of memory it needs to run to completion.
The time complexity of an algorithm is the amount of computer tume it needs to run to com
pletion. ~
Performance evaluation can be loosely divided into two major phases:
(1) A priory estimate arid (2) a posteriori testing. We refer to these performance-analysis
and performance measurements respectively.
Space complexity
(IA fixed part that is independent of characteristics (e.g., number, size) of the inputs and
outputs this part typically includes the instruction space (i.e. space for code), space for
simple variables and fixed size component variables (also called aggregate),space for con-
stants and so on.
(2) A variable part that consist of space needed by component variable whose size is de-
pendent on particular problem instance being solved, the space needed by referenced va-
riables (to the extent that it depends on instance characteristics), and the recursion stack
space (insofar and this space depends on the instance characteristics). The space require-
ment S(P) of an algorithm P may therefore be written as S(P) =c + Sp (instance characte-
ristics),where c is constant. When analyzing the space complexity of an algorithm, we
concentrate solely on estimating Sp (instance characteristics). For any given problem, we
“4need first to determine which instance ch;
Mt. Generally speaking our choices
Puts to and outputs from the
aracteristics to use to measure
ine the space require-
Are related to the number and magnitude of the in.
At times, more complexity measures of the intere-
are used.
algorithm
lationship among the data times
Time complexity
The time T (P) taken by a program P is
does not depend on the instance char
Because of many of the factor tp depends on are not Known at the time of a program is con-
ceived, it is reasonable to attempt only to esti
imate tp. If we knew the characteris
Piler to be used, we could
Proceed to determine the number of additions, Subtractions, multiplication, divisions,
com-
Pares, loads, stores and so on, that would be made by the code for P” So, we could obtain an
expression for t, (n) of the form
t(n)=c,ADD(n)+c,SUB(n)+¢,MUL(n)+e,DIVin)+...
Where n denotes the instance characteristics and ea, ¢ CmyCa, and So on, respectively, dencte
the time needed for an addition subtraction, multiplication, division and so on, and ADD,
SUB.MUL,DIV, and so on are the functions whose values are numbers of additions
subtractions, multiplication, division and soon ,that are performed when code for P is used on
an instance with characteristics n. a
Obtaining such an exact formula is in itself an impossible task, Since the time needed for addi-
tion, subtraction, multiplication, and so on, depend on the number being added, and subtract,
multiplication and so on. The value of tp (n) for any given n can be obtained only experimea-
tally. The program is typed, compiled, and run on a particular machine, The execution time is
physically clocked, and tp (n) obtained. Even with this experimental approach, one could face
difficulties. In a multiuser system, the execution time depends on such factors as system load,
the number of other programs running on the computer at the time program P is run, the cha-
racteristics of these programs, and so on.i subtract and so
rol jons, subtraction,
Given the minimal utility of determining the exact number of additi
ce with characteristics given by n, we might as
on, that are needed to solve a problem in:
¢ er of operations .We
well lump all the operations together and obtain a cont for the total number of op
can go one more step further and count only the number of program steps.
i ‘a i nt of a
A program step is loosely defined as a syntifctically or semantically meaningful segmet
, ; z F ae
program that has an execution time that is independent of the instance characteristics. For
ample. the entire statement
Return at+b+b*c+(atb-c)/(atb) +4.
Of Algorithm 1.5 could be regarded as a step since its execution time is independent of the
instance characteristics (this statement is not strictly true , since the time for a multiply and
divide generally depends on the numbers involved in the. operation). — —
‘The number of steps any program statement is assigned depends on the kind of statement. For
example comments count as zero steps; an assignment statement which-does not involve calls
any to other algorithms is encountered as one step; in an iterative statement such as for, while
and repeat until statement, we consider the step count only for control part of the statement.
The control parts for and while statements have the following form:
for i=to do
while () do
each execution of the control part of a while statement is a step count equal to the number of
Step counts assignable to .the step count for each execution of control part of a for
Statement is one, unless the count attribute to ‘ and are functions of the in-
stance characteristics . In this latter case the first execution of the control part of the for has
SteP count equal to the sum of counts for and .remaini
statement have a step count of‘one; and so on.
Ing executions of the for
We can determine number of steps needed by program to solve @ particular problem instance
in one of the two ways. in the first method we introduce a new Variable count ,into the pro-
Sram his is the global variable with initial value 0. statement ‘o increment count by appropri-
ate amount are introduced into the program. this is done so that each time a statement in the
Original program is executed ,count is incremented by step count of that statement.14 Important Problem Types
© Sorting
+ Searching 5
© String processing
Graph problems
* Combinatorial problems
‘© Geometric problems
+ Numerical problems
sorting algorithm is an algorithm that puts elements of a ist im-a certain order. The most=—
used orders are numerical order and Jexicographical order. Efficient sorting is important to
optimizing the use of other algorithms (such as search and merge algorithms) that require
sorted lists to work correctly; itis also often useful for canonicalizing daja and for producing
human-readable output. More formally, the output must satisfy two conditions:
1, The output is in nondecreasing order (each element is no smaller than the previous
element according to the desised total order);
2. The output is a permutation, o1.reordering, of the input. —
Since the dawn of computing, the sorting problem has attracted a great deal of research, per-
haps due to the complexity of solving it efficiently despite its simple, familiar statement. For
example, bubble sort was analyzed as early as 1956." Although many consider it a solved
problem, useful new sorting algorithms are still being invented (for example, library sort was
first published in 2004). Sorting. problem provides a gentle introduction to a variety of core
algorithm concepts, such as big O notation, divide and conquer algorithms, data structures,
randomized algorithms, best, worst and average case analysis, time-space tradeoffs, and lower
bounds. . :
‘Searching : In computer science, a search algorithm, broadly speaking, is an algorithm for
finding an item with specified properties among a collection of items. The items may be
stored individually as records in a database; or may be elements of a search space defined by a
mathematical formula or procedure, such as the roots of an equation with integer variables; or
a combination of the two, such as the Hamiltonian circuits of a graph Searching algorithms
are closely related to the concept of dictionaries. Dictionaries are data structures that support
search, insert, and delete operations. One of the most effective representations is a hash table.
Typically, a simple function is applied to the key to determine its place in the dictionary.
Another efficient search algorithms on sorted tables is binary search|o
String processing:String searching algorithms are important in all sorts of applications that
we meet everyday. In text editors, we might want to search through a very large document
(say, a million characters) for the occurence of a given string (maybe dozens of characters). In
text retrieval tools, we might potentially want (o search through thousands of such documents
(though normally these files would be indexed, making this unnecessary). Other applications
might require string matching algorithms as part of a more complex algorithm (e.g., the Unix
program “diff” that works out the differences between two simiar text files). Sometimes we
~might want to Search in binary strings (ie; sequences of Os-and-1s)- For example the ~*pbm'
graphics format is based on sequences of Is and Os. We could express a task like “find a wide
white stripe in the image” as a string searching problem. _
Graph problems:Graph algorithms are one of the oldest classes of algorithms and they have
been studied for almost 300 years (in 1736 Leonard Euler formulated one of the first graph
»blems Kénigsberg Bridge Problem) Tacctia paced
probler igsberg Bridge Problem) ao dind qraey anki es
DS
‘There are two large classes of graphs: AG
él
+ directed graphs (digraphs ) © So g
+ _undirected graphs
‘Some algorithms differ by the class. Moreover the set of problems for digraphs and undirected
gyaphs are different. There ae special cass of digraphs and graphs that have thes own Sts
of problem. One example for digraphs will be program graphs. Program graphs are important
in compiler construction and were studied in detail after the invention of the computers.
Graphs are made up of vertices and edges. The simplest property of a vertex is its degree, the
number of edges incident upon it. The sum of the vertex degrees in any undirected graph is,
twice the number of edges, since every edge contributes one to the degree of both adjacent
vertices. Trees are undirected graphs which contain no cycles, Vertex degrees are important in
the analysis of trees. A leaf of a tree is a vertex of degree 1. Every Mt-vertex tree contains
™ ~ edges, so all non-trivial trees contain at least two leaf vertices.Among classic algorithms/problems on digraphs we can note the following
+ Reachability. Can you get to B from A?
+ Shortest path (min-cost path). Find the path from B to A with the minimum cost (de-
termined as some simple function of the edges traversed in the path) (Dijkstra’s and
Floyd's algorithms) -
+ Visit all nodes. Traversal. Depth- and breadth-first traversals
+ Transitive closure. Determine all pairs of nodes that can reach each other (Floyd's al-
gorithm)
+ Dominators a node d dominates a node n if every path from the start node to n must
80 through d. Notationally, this is written as d dom n. By definition, every node domi-
nates itself. There are a number of related concepts:
© immediate dominator
© pre-dominator
© post-dominator.
© dominatortree a
+ Minimum spanning tree. A spanning three is a set of edges such that every node is.
reachable from every other node, and the removal of any edge from the tree eliminates
the reachability property. A minimum spanning tree is the smallest such tree. (Prim's
and Kruskal's algorithms)
Combinatorial problems: From a more abstract perspective ,the traveling Salesman problem
and the graph coloring problems of combinatorial problems are problems that a task to find a
combinatorial objectsuch as permutation a combination ,or a subset-that satisfies certain
constraints and has some desired property.Generally speaking, combinatorial problems are the
most difficult problems in computing from both the theoretical and practical standpoints.
Their difficulty stems from the following facts. First ,the number of combinatorial objects
typically grows extremely fast with a problem size , reaching unimaginable magnitudes even
‘moderate-sized intances. Second, there are no known algorithms for solving most such prob-
lems exactly in an acceptable amount of time. Moreover, most computer scientist believe
such algorithms do not exist. This conjecture has been neither proved nor disproved ,and it
remains the most important resolved issue in theoretical computer science,
Some combinatorial problems can be solved by efficient algorithms, but they should be
considered fortunate to the rule. The shortest-problem mentioned earlier is among such excep-
Geometric Problems
Geometric algorithms deal with geometric objects such as points , lines, and polygons. An-
cient Greeks were very much interested in developing procedures for solving a variety of -
geometric problems including problems of constructing simple geometric shapes-triangles
VV of vertices where vo
= vv = mand (vj Vis) EE for 1 = 0, Iyonu kel.
The length of a path is defined as the number of edges in the path
@) (b)
Figl.g. A directed undirected graph.
Graph Properties -- Acyclicity
Cycle
| = A simple path of a positive length that starts and ends a the same vertex.
Acyclic graph
= A graph without cycles
- DAG (Directed Acyclic Graph)
+ Paths and Connectivity Paths :
— Apath from vertex u to v of a graph G is defined as a sequence of adjacent
(connected by an edge) vertices that starts with u and ends with v.
. Simple paths: All edges of a path are distinct.
Path lengths: the number of edges, or the number of vertices ~ 1.Connected graphs
A graph is said to be connected if for every pair of its vertices w and v there is a
path from wto y
Connected component
~The maximum connected subgraph of a given graph
Graph Representation ; A graph is represented by (6)
row many Wap graph Caw be AoPenenteut
+ Adjacency matrix .
nx n boolean matrix if IVlis n.
~The element on the ith row and jth column is 1 if there's an edge from ith ver-
tex to the jth vertex; otherwise 0.
— The adjacency matrix of an undirected graphi is symmetci.
+ Adjacency linked lists -
A collection of linked lists, one for each vertex; that contain’all the vertices adjacent to the
list’s vertex
©1000
19:04
A= fo 10 028
oo 0 O14
= o 21 3: 9]
=a
a
wu
LJ:
ay
Figl.h.Graph representation.FUNDAMENTALS
ait 4)
Tadagsavauet , (SMSL7
BRougelae.
OF THE ANALYSIS OF ALGORITHM
EFFICIENCY
Analysis of algorithms means to investigate an algorithm's efficiency with
respect to resources:
© running time (time effi
icieney ) and.
‘© memory space ( space efficiency )
Time being more critical than space, we concentrate on Time efficiency of algorithms
The theory developed, holds goo
od for space complexity also.
Experimental Studies: requires writing @ program implementing the algorithm and
running the program with inputs of varying size and composition. It uses a function, like
the built-in clock() function, to
get an accurate measure of the actual running time, then
analysis is done by plotting the results.
Limitations of Experiments
+ Itis necessary to implement the algorith
- whielrmay be difficult —
2 Results may not be indicative of the running time on other inputs not included in
the experiment.
_ + In order to compare
environments must be us
Theoretical Analysis: It uses
two ‘algorithms, the same hardware and software
ed - -
a high-level description of the algorithm instead of an
implementation. Analysis characterizes running time as a function of the input size, n-
‘and takes into account all possible inputs. This allows us to evaluate the speed of an
algorithm independent of the
hardware/software environment. Therefore theoretical
analysis can be used for analyzing any algorithm
Framework for Analysis
We use a hypothetical model with following assumptions
+ Total time taken by the algorithm is given as a function on its input size
+ Logical units are identified as one step
+ Every step require ONE unit of time
+ Total time taken = Total
Num. of steps executed
~
Input’s size: Time required by an algorithm is proportional to size of the problem
instance. For e.g., more time is required to sort 20 elements than what is required to sort
10 elements.
Units for Measuring Running
‘Time: Count the number of times an algorithm’s basic
operation is executed. (Basic operation: The most important operation of the algorithm,
the operation contributing the
The basic
most to the total running time.) For e.
operation is usually the most time-consuming operation in the algorithm's innermost
loop.Consider the following example:
ALGORITHM sum_of_numbers ( A[0... n-1])
4 Functionality : Finds the Sum
Y/ Input : Array of n numbers
Y Output : Sun of ‘n’ numbers
i€o
sum €0
while in0
g(r)
ae 100M + SCloone
: (oe a l)zlos
My comple te pa
— Sth Clore ie
Big-oh notation: t(n) € O(g(n))
es Joon ts EobY
foone ® (fu at 875)
a
= yo\in com a se |
Canstant Cad me Recsiered by Ble hatin Gin poe can |
S aatpeiu zospecthruly
falee, lol avd = ;
fy dor fo Chose Apeckc Untuas forcontaut Cart
a
Joona © &
— 1Pie as
zy
“4
“Big Omega- Q notation
Definition:
A function t (n) is said to be in Q (gin)), denoted tn) € 2 (g (n)), if t (n) is bounded
below by some constant multiple of g (n) for all large n, ic., if there exist some positive
‘Constant ¢ and some nonnegative integer nO such that
An) 2 eg(n) for all n> no
er: Ed oY
« wt x) nttor 070
egtn) equ Bele
Cal are Moro
rewe
Big-omega notation: t(n) € 9(9(n))
Big Theta- @ notation
Definition:
‘A function t (n) is said to be in @(g (n)), denoted t(n) € oe ()), if t (a) is bounded both
above and below by some constant multiple of g (n) for all large n, i.e, if there exist
some positive constant cl and c2 and some nonnegative integer n0 such that
2g (n) St(n) z 4
~ pre test a leone J
Seeod We Ln l 5 Ho 4
J nce) = ant toa
e
ecu select Ce op Sh
peneEfficiency classes
‘The time efficiencies of a large number of algorithms fall into only a few classes.
fast 1 constant
logn logarithmic
n linear
nlogn nlogn
vr quadratic
nt cubic
2 ~ — |exponéntial
nt factorial
slow
High time efficiency
Tow time efficiency
Mathematical analysis (Time Efficiency) of Non-recursive Algorithms
General plan for analyzing efficiency of non-recu
1. Decide on parameter.n indicating input size
2. Identify algothm’s basic operation
e algorithms:
3. Check whether the number of times the basic operation is executed depends only
‘on the input size n. If it also depends on the type of input, investigate worst,
average, and best case efficiency separately.
4. Set up summation for C(n) reflecting the number of times the algorithm’s basic
operation is executed,
5. Simplify summation using standard formulas
Example: Finding the largest element in a given array
ALOGORITHM MaxElement(A[0..n-1})
ae
“etermines the value of largest element in a given array
Minput: An array A[0..n-1] of real numbers
Output: The value of the largest element in A
currentMax € A[0]
fori 1ton—1do
if Afi] > currentMax
currentMax — Afi)
return currentMaxe: number of clements = n (size of the array)
2. Basic operation
a) Comparison
b) Assignment
3. NO best, worst, average cases,
4. Let C (n) denotes number of comparisons: Algorithm makes one comparison on
each execution of the loop, which is repeated for each value of the loop’s variable
i within the bound between J and n— 1.
Cn)= Sai
isd
5. Simplify summation using standard formulas
n-1
L+lalead
C= 1.__{(n-1) number of times}
C@=n-1
C@@) S41
{=O jen
5. Simplify summation using standard formulas
ns?
C@)= S@-1)-G4D41)
&
22
cC@= pat (n-1-i)
= .
2 ; -
Sov yr Okara orm}
me ayn)
cw= on F1 - aoe
a2
C@=a-)> 1 6c
&
~~ Ce (n=
CMs @-Vna1) - OH 7@=)
(n-1)- a »|
C(n)= (n= 1) Qn-2-n+2)
2
C@= @-1
C= ln) 2
On
-- aD
" ie en ¢
Ned +
aot ENVe
s (Time Efficiency) of recursive Algorithms
General plan for analyzing efficiency of recur:
Mathematical anal
ive algorithms:
1. Decide on parameter n indicating input size
2, Identify algorithm's basic operation
3. Check whether the number of times the basic operation is executed depends only
on the input size n. If it also depends on the type of input, investigate worst,
average, and best case efficiency separately.
4. Set up recurrence relation, with an appropriate initial condition, for the number
of times the algorithm's basic operation is executed,
5. Solve the recurrence.
Example: Factorial function
ALGORITHM Factorial (n)
“Computes n! recursively
Mnput: A nonnegative integer n
WOutput: The vate of nt
ifn
return i
ese -
return Factorial (n — 1) * n
Analysis:
1, Input size: given number =n
2. Basic operation: multiplication
3. NO best, worst, average cases.
4. Let M (n) denotes number of multiplications.
M(n)=M(n-1)41 forn>0
MO) initial condition
Where: M(n—1): to compute Factorial (n—1)
1 :to multiply Factorial (n — 1) by n
5. Solve the recurrence: Solving using “Backward substitution method”
- M(n) =M(@-1)+1
=(M(n-2)+1] +1
M(n-2)+2
M(n-3)+1] +3
=M(n-3)+3
In the ith recursion, we have
=M(n-i)+i
‘When i =n, we have
“=M(n-n)+n=M(0)+n
Since M (0) =0
=n
M(n)e O(n)p-24
Examplé: Find the number of binary digits in the binary representation of a positive
decimal integer
ALGORITHM BinRee (1)
Mnput: A positive decimal integer n
Output: The number of binary digits in n's binary representation
ifn==1
return |
else
return BinRec (“n/24) +1
Analysi
1. Input size: given number = n
2. Basic operation: addition
3. NO best, worst, average cases.
4. Let A (n) denotes number of additions.
ngd)+ 1
€ initial condition
Where: A (4 2/24) : to compute BinRec (+ n/2 4)
1: to increase the returned value by 1
5. Solve the recurrence:
A@=A(Ln24)+1 forn> 1
Assume n = 2* (smoothness rule)
A (2) =A (2*1) +1 fork >0; At20y=0
Solving using “Backward substitution method”:
AQSAQ) +1
=(AQ*) +1) +1
=A) +2
=(AQ**) +1] +2
=A) 43
In the ith recursion, we have
SAO) +i
When i= k, we have
=A) +k =AQ)+k
Since AQ) oy
AQ a
Since n= HENCE k= logs n
A(a)= logon
A(n)€ © (log n)
forn> 1.
pn(f) 26
ib a=
ole okie Byavec(hfr) +
AW) aly) + rn)
Ml ro
Solve
~ apy = a) fo"
ayer
tea) “naan vale
ies
a “yg Bacieword a
yore” ict
AW = >
Ae
7)
“sets
+\
aya
iN
va
ate
or
ken t2 BR whee
ph) = ae) tk
grace G2) =0
aie ="
pu koeFk Eis COlogny) ave td C0 @fo Frey
tit) 4tiw COC mad Gi ¢ o.by
| Pret e- sey
) cour orbitee ty
dak Ay by ae aed br ac yeal numbers [ oveler ¢ grow ta
ik a) ob, art @ Sbe ~
spew aean © > warlbres
gue £0 COW) A Som pent cashit Cy atel
Bowe NM yogclie jutser h, 2
tir) c.g fo ath WM)
Ny tab» €0@W)
tow é cla.) fe Sl WOME =
Jot vs dono ¢y = may (Cr ty g Concer 1 gy masd ib £0
afrot We Con We both jue Bs eRetei ny “The Hes9 VA emake ly
Chew qickels he follo oY
bi + tee nicvesecre?
x yor . o
ot? ; gio ON ee
7 eo ae
oy | | |
&milliSe acta 5 .
pbs 7
~ Tawlis
