People’s Democratic Republic of Algeria

Ministry of higher education and scientific research

University of Mohamed Boudiaf - M’sila

Faculty of Mathematics and Computer Science

Department of Computer Science

2nd Year License (2L)

Data Structures and Algorithms 3

(DSA3)

Semester : 03 Directed by
2024/2025 Dr. DABBA ALI
 Contact us
alidabba@[Link]
[Link]@[Link]

 In case of problems or difficulties, please contact

me or your TD / TP teacher.
 We are at your disposal to help you
CHAPTER 1

Algorithm Analysis
 Plan
I. Introduction
II. Data Structure
III. What is an Algorithm?
IV. Algorithm Analysis
V. Algorithm Complexity
VI. Mathematical Notation
[Link]-Time Calculations
Dr. Dabba Ali 4
 I. Introduction
Problem Algorithm Result

Efficiency
of an Data
algorithm
Efficiency of an algorithm can be measured in terms of:
 Execution time (time complexity)
 The amount of memory required (space complexity)
 II. Data Structure
Linus Torvalds (creator of Linux)
“ I will, in fact, claim that the difference between a bad
programmer and a good one is whether he considers his
code or his data structures more important. Bad
programmers worry about the code. Good
programmers worry about data structures and their
relationships. ”
 II. Data Structure
 Data structure is a particular way of storing and
organizing data in a computer so that it can be
used efficiently.
 A data structure is a special format for organizing
and storing data.
 General data structure types include arrays, files,
linked lists, stacks, queues, trees, graphs, and so
on.
 II. Data Structure
Integer

Real
Primitive data
structure
Character
Arrays
Boolean
Data structure Linked
Linear data
structures
Stacks
Non-primitive data
Queues
structures
Trees
Non-linear data
structures
Graphs
 III. What is an Algorithm?
Algorithm is a step-by-step procedure to solve a
problem, where each step indicates an intermediate task.
Algorithm contains a finite number of instructions to be
executed in a certain order to get the desired output.
Algorithms are generally created independent of
underlying languages, i.e., an algorithm can be
implemented in more than one programming language.
 III.1. Characteristics of Algorithms
The main Characteristics or features of Algorithms are:
 Input  Output

 Definiteness  Finiteness
 Effectiveness
 Feasible
 Language Independent
 III.2. Advantages of Algorithms
 Easy: Algorithm is easy to understand.
 Reusability: Once developed, algorithms can be reused
in different applications and scenarios, reducing the
need to start from scratch each time.
 Scalability: Good algorithms can handle varying input
sizes without a significant increase in resources.
 III.3. Disadvantages of Algorithms

 Complexity: Designing and implementing algorithms

can be complex, especially for intricate problems.
 Branching and Looping statements are difficult to
show in Algorithms.
 IV. Algorithm Analysis
The analysis is a process of estimating the efficiency of an
algorithm and that is, trying to know how good or how bad an
algorithm could be. There are two main parameters based on
which we can analyze the algorithm:
 Space complexity can be understood as the amount of space
required by an algorithm from its run to its completion
 Time complexity is a function of the input size that
indicates the amount of time required by the algorithm from its
run to its completion.
 IV.1. Execution Time / Runtime
 Usually, program execution time (program run-time) is referred
to as time complexity, denoted by (instance
characteristics). This is the sum of the execution times of all
program instructions.
 Accurately estimating the execution time is a complex task,
since the number of instructions executed depends on the
input data.
 What's more, the various instructions take varying amounts of
time to execute. So, when estimating time complexity, we only
count the number of program steps.
 IV.1.1. Runtime Based on a Single Parameter
Let be an algorithm and the function such that denotes

∶
the number of elementary operations performed by on input .

ℕ → ℕ such that:
The execution time of in the worst case is the function

: .
In other words, indicates the largest number of operations
performed among all inputs of size .
 IV.1.1. Runtime Based on a Single Parameter
Example:

The code below finds the sum of numbers.

Determine the number of steps in this program.
We consider the following operations to be
elementary: assignment, comparison, addition
and access to an element of a sequence.
 IV.1.1. Runtime Based on a Single Parameter
Statement Operations Frequency Total steps
float Sum(float a[], int n){ 0 / - 0
float s=0.0; 1 Assignment 1 1
int i=0; 1 Assignment 1 1
while(i<n){ 1 comparison n+1 n+1
s = s + a[i]; 3 add, Ass, access n 3n
i = i+1; } 2 add, Ass n 2n
return s;} 0 / - 0
Algorithm (function)
Total T(n)= 6n+3
works in linear time
 IV.1.2. Runtime Based on Several Parameters
For some algorithms, the "size" of an input depends on several
parameters, e.g., the number of rows and columns of a matrix;
the number of elements of a sequence and the number of bits
of its elements; the number of vertices and edges of a graph,
and so on. For these algorithms, the notion of time is naturally
extended:
,..., : ,..., .
 IV.1.2. Runtime Based on Several Parameters
Example:
The code below calculates the addition of two matrices
of size .
 Determine the number of steps in this program.
 We consider the following operations to be elementary:
assignment, comparison, addition and access to an
element of a matrix.
 IV.1.2. Runtime Based on Several Parameters
Statement Operations Frequency Total steps
void Add(Type a, b, m, n){ 0 / - 0
int i=0; 1 Assignment 1 1
while (i < m){ 1 comparison m+1 m+1
int j =0; 1 Assignment m m
while (i < n){ 1 comparison m(n+1) m.n+m
c[i][j]=a[i][j]+b[i][j]; 5 add, Ass, acc m.n 5(m.n)
j = j+1;} 2 add, Ass m.n 2(m.n)
i = i+1; }} 2 add, Ass m 2m
Total T(m, n)= 8mn+5m+2
IV.1.3. Types of Time Complexity Analysis
Example: Find a given value (if it exists!) in this array

0 1 2 3 4 5 6 7 8 9
15 25 3 7 33 28 7 9 10 11

15 OK

⇒ Best-case
IV.1.3. Types of Time Complexity Analysis
Example: Find a given value (if it exists!) in this array

0 1 2 3 4 5 6 7 8 9
15 25 3 7 33 28 7 9 10 11
OK

11 11 11 11 11 11 11 11 11 11

⇒ Worst-case
IV.1.3. Types of Time Complexity Analysis
IV.1.3. Types of Time Complexity Analysis
We have three types of analysis related to time complexity:
 Worst-case time complexity: For 'n' input size, the worst-case
time complexity can be defined as the maximum amount of
time needed by an algorithm to complete its execution.
Thus, it is nothing but a function defined by the maximum
number of steps performed on an instance having an input size
of n. Computer Scientists are more interested in this.
 Big-O Notation
IV.1.3. Types of Time Complexity Analysis
We have three types of analysis related to time complexity:
 Average case time complexity: For 'n' input size, the average
case time complexity can be defined as the average amount of
time needed by an algorithm to complete its execution.
Thus, it is nothing but a function defined by the average number
of steps performed on an instance having an input size of n.

 Big-Theta (Θ) Notation

IV.1.3. Types of Time Complexity Analysis
We have three types of analysis related to time complexity:
 Best-case time complexity: For 'n' input size, the best-case
time complexity can be defined as the minimum amount of
time needed by an algorithm to complete its execution.
Thus, it is nothing but a function defined by the minimum
number of steps performed on an instance having an input size
of n.
 Big-Omega (Ω) Notation
 V. Algorithm Complexity
 The term algorithm complexity measures how many steps are
required by the algorithm to solve the given problem.
 It evaluates the order of count of operations executed by an
algorithm as a function of input data size.
 To assess the complexity, the order (approximation) of the
count of operations is always considered instead of counting
the exact steps.
 V. Algorithm Complexity
 O(f) notation represents the complexity of an algorithm, which
is also termed an Asymptotic notation or "Big O" notation.

∗
 The complexity can be found in any form such as constant,
logarithmic, linear, , quadratic, cubic,
exponential, factorial etc.
 To make it even more precise, we often call the complexity of
an algorithm "running time".
 VI. Mathematical Notation
 Algorithms are widely used in various fields of study.

 We can solve different problems using the same algorithm.

Consequently, all algorithms must respect a standard.

 Mathematical notations use symbols or symbolic

expressions that have a precise semantic meaning.
 VI.1. Asymptotic Notations
To select the best algorithm, it is necessary to check the efficiency
of each algorithm. The efficiency of each algorithm can be
verified by calculating its time complexity. Asymptotic notations
are used to represent time complexity in an abbreviated form.
 Big-O Notation : Worst-case time complexity.
 Big-Theta (Θ) Notation : Average case time complexity.
 Big-Omega (Ω) In this course,
Notation we'll focus
: Best-case timeon
complexity.
the Big-O notation.
 VI.1.1. Big-O Notation
 Big-O notation is a mathematical notation used to describe the
upper bound or worst-case scenario of the time
complexity or space complexity of an algorithm in computer
science.
 It provides a way to classify algorithms based on how their
runtime or space requirements grow as the input size increases,
 Generally, it is represented as f(n) = O(g(n)). That means, at
larger values of n, the upper bound of f(n) is g(n).
 VI.1.1. Big-O Notation
Definition I.1
We consider functions from ℕ to ℝ that are eventually positive, i.e., functions

:ℕ → ℝ ∶ ∃ ∈ ℕ, ∀
belonging to:

∈
∈ :∃ ∈ ℝ ,∃ ∈ ℕ, ∀ .
Let . The set is defined by:

 Intuitively, ∈ indicates that increases as quickly or less

quickly than the function .
 We call the values c and a multiplicative constant and a threshold.
 VI.1.1. Big-O Notation
 The graphical representation of f(n) = O(g(n)) is shown in the
figure, where the running time increases considerably when n
increases.
Rate of Growth

Input Size
 VI.1.1. Big-O Notation
Example:

 Consider the function

 The function is greater than

 However, we can show that ∈ .

 VI.1.1. Big-O Notation
Example:
We have :

.
for all
for all

∈
 Thus, taking as a multiplicative constant and
as a threshold, we conclude that .
 VI.1.1. Big-O Notation
Example:

∈ .
 VI.1.2. Big-O Notation for Complexity Class
The most common complexity classes (in increasing order) are the following:







!




 VI.1.2. Big-O Notation for Complexity Class

. .
.
1 1 1 1
.
.
1 2 3
.
. .
2 4 8
.
. .
4 16
.
. .
8 64
.
. .
16 256
.
.
64 4096
16 65536 . .
 VI.1.2. Big-O Notation for Complexity Class

1 1 µsec 1 µsec 1 µsec

. .
µsec µsec
1 µsec 2 µsec 3 µsec µsec µsec
2 µsec 4 µsec 8 µsec
. . .
µsec µsec
4 µsec 16 µsec msec sec
. .
µsec
8 µsec 64 µsec msec msec sec
16 µsec 256 µsec . msec . sec . wk
64 µsec 4.1 msec . sec . min . yr
16 µsec 65.5 msec . yr . yr . yr
VI.1.2. Big-O Notation for Complexity Class
VI.1.3. Properties of Asymptotic Notations
a) General (Constant Factor)
If
e.g.,
,
VI.1.3. Properties of Asymptotic Notations
b) Reflexive
Given , , since maximum value of
will be itself, i.e., every function is an upper-bound
of itself.
e.g.,
VI.1.3. Properties of Asymptotic Notations
c) Transitive
,

, ,
&
e.g.,

⟹
here,
 VI.1.4. Limitations of Big O Notation
 Many algorithms are too hard to analyze mathematically.
 Big-O analysis only tells us how the algorithm grows with
the size of the problem, not how efficient it is, because it does
not consider the programming effort.
 It does not take into account important constants. For
example, if one algorithm takes time to execute and the
other takes time to execute, then according to
Big O, both algorithms have the same time complexity. In real-
time systems, this is an important consideration.
 VII. Running-Time Calculations
 There are several ways to estimate the running time of a
program. To simplify the analysis, we will adopt the convention
that there are no particular units of time.
 We are essentially doing is computing a Big-Oh running
time. Since Big-Oh is an upper bound, we must be careful never
to underestimate the running time of the program.
 In effect, the answer provided is a guarantee that the program
will terminate within a certain period.
 VII.1. Assumptions in Complexity Analysis
 Uniform Cost Model: Assumes that all basic instruction (such
as arithmetic, comparisons, assignments, . . . ) have the same
cost. This simplifies the analysis by treating each operation as
taking constant time, represented by the notation O(1).
 Input size: Analysis is generally performed based on the input
size, often referred to as “n”, which represents the number of
elements or the size of the input data structure.
 VII.1. Assumptions in Complexity Analysis
 Worst-case scenario: Complexity analysis often focuses on the
worst-case input, i.e., assuming the input that leads to the
maximum number of operations.
 Loops: each iteration of a loop adds the complexity of what is
done in the loop body.
 Functions (procedures): each function call adds the
complexity of that function to the total complexity.
 VII.2. Simplification Rules
 Drop Constants: Constants in front of the dominant term are
dropped in Big-O notation. For example: simplifies to
.
 Dominant Term Rule: only the term with the largest growth rate
dominates in Big-O notation. For example, in , a
dominant term is , so the complexity is .
 Additive Rule: When analyzing multiple operations in sequence, the
complexities are added. For example, if an algorithm has two

.
separate loops with complexities and , the total
complexity is
 VII.2. Simplification Rules
 Multiplicative Rule: When analyzing nested operations, the
complexities are multiplied. For example, if an algorithm has

∗
nested loops with complexities and , the total
complexity is .

 Logarithmic Rules: Base of logarithms can be ignored in Big-

O notation, as they represent constant factors. Therefore,
and are considered the same.
VII.3. How to Calculate the Approximate Time
Taken by the Algorithm?
First, we need to understand the types of algorithms available to us.
There are two types of algorithms:
 Iterative algorithm: In the iterative approach, the function
executes repeatedly until the condition is met or it fails. It
involves the construction of a loop.
 Recursive Algorithm: The function calls itself until the
condition is met in the recursive approach. It integrates the
branching structure.
 VII.4. Guidelines for Asymptotic Analysis of
Iterative Algorithms
There are some general rules to help us determine the running time
of iterative algorithms
 Simple Statement and O(1)
 Sequence of Simple Statements
 Sequence of Statements
 Selection
 Iterations (Loops)
 VII.4.1. Simple Statement and O(1)

 We define a simple statement as one that does not have any

control flow component (subprogram call, loop, selection,
etc.) in it.
 An assignment is a typical example of a simple statement.
 Time taken by a simple statement is considered to be constant.

1 Operation (assig) ⟹
E.g.,
int x = 1;
 VII.4.1. Simple Statement and O(1)

 Let us assume that a given simple statement takes units of

time. If we factor out the constant, we would be left with 1,
yielding = (1). That is, a constant amount of time is denoted
by (1). It may be noted that we are not concerned with the
value of the constant; as long as it is constant, we will have (1).

1 Operation ⟹ k units of time ⟹

E.g.,

2 Operations ⟹ g units of time ⟹

int x = 1;

x=x+1;
 VII.4.2. Sequence of Simple Statements

 As stated above, a simple statement takes a constant amount of

time. Therefore, time taken by a sequence of such statements
will simply be the sum of time taken by individual statements,
which will again be a constant. Therefore, the time complexity
of a sequence of simple statements will also be .
E.g.,
int x = 1;
x=x+1;
 VII.4.3. Sequence of Statements

 Time taken by a sequence of statements is the sum of time

taken by individual statements which is the maximum of these
complexities.
E.g.,
statement1 //
statement2 //
statement3 //
statement4 //
 VII.4.4. Selection

A selection can have many branches and can be implemented with

the help of or tch statement. In order to determine the time
complexity of an or ch statement,
 we first independently determine the time complexity of
each one of the branches separately.
 Since, in a selection, each branch is mutually exclusive, the
worst-case scenario would be the case of the branch which
required the largest amount of computing resources.
 VII.4.4. Selection

Example:
if (cond1) statement1 //
else if (cond2) statement2 //
else if (cond3) statement3 //
else statement4 //
The time complexity of this code segment will be:
 VII.4.5. Iterations (Loops)

 In C (C++) language , h , and − h statements

are used to implement an iterative step or loop.
 Complexity analysis of iterative statements is usually the most
difficult of all the statements.
 The main task involved in the analysis of an iterative statement
is the estimation of the number of iterations of the body of
the loop.
 There are many different scenarios that need separate attention
and are discussed below.
 VII.4.5. Iterations (Loops)

 There are many different scenarios that need separate attention

and are discussed below.
 Simple Loops
 Loops with Uniform Step Size
 Simple Loops with Variable Step Size
 A Deceptive Case
 Nested Loop
 Independent Loops
 Dependent Loops
 VII.4.5.1. Simple Loops

We define a simple loop as a loop which does not contain another

loop inside its body (that is no nested loops). Analysis of a simple
loop involves the following steps:
1. Determine the complexity of the code written in the loop
body as a function of the problem size. Let it be .
2. Determine the number of iterations of the loop as a function
of the problem size. Let it be .

. .
3. Then the complexity of the loop would be:
 VII.4.5.1. Simple Loops

Example:

for( i = 1; i <= n; i ++) number of iterations

S = S + 2; // constants time, is n,

Total time = .
 VII.4.5.2. Loops with Uniform Step Size

 As stated above, we define a simple loop with uniform step size

as the simple loop where the loop control variable is
incremented/decremented by a fixed amount.
 That is, in this case, the values of the loop control variable
follow an algebraic sequence. These are perhaps the most
commonly occurring loops in our programs.
 These are usually very simple and have a time complexity of
( ). They are also very simple to analyze.
 VII.4.5.2. Loops with Uniform Step Size

Example: The following code for Linear Search elaborates this in

more detail.
index = -1; //
for (int i = 0; i < N; i++) //
if (a[i] == key) { //
number of iterations
index = i; // is n,
break; //
} //for
 Total time = .
 VII.4.5.2. Loops with Uniform Step Size

We can easily see that:

 Time complexity of the code in the body of the loop is
 In the worst case (when key is not found), there will be n
iterations of the for loop, resulting in .
 Therefore, the time complexity of the Linear Search algorithms
is: .
VII.4.5.3. Simple Loops with Variable Step Size

 In loops with variable step size, the loop control

variable is increased or decreased by a variable
amount.
 In such cases, the loop control variable is usually
multiplied or divided by a fixed amount, thus it
usually follows a geometric sequence.
VII.4.5.3. Simple Loops with Variable Step Size

Example: The following code for Linear Search elaborates this in

more detail.
high = N-1;
low = 0;
index = -1;
while(high >= low)
{
mid = (high + low)/2; number
if (key == a[mid]) { index = mid; break;} of
else if (key > a[mid]) low = mid + 1;
else high = mid – 1;
iterations
} ???
VII.4.5.3. Simple Loops with Variable Step Size

Example: The following code for Linear Search elaborates this in

more detail.
 Once again, we can easily see that the code written in the
body of the loop has a complexity of .
 We now need to count the number of iterations.
 VII.4.5.3. Simple Loops with Variable Step Size
Example: The following code for Linear Search elaborates this in
more detail. mid
OK
low mid low high mid high
index

0 1 2 3 4 5 6 7 8 9
5 8 13 19 25 28 37 49 50 64

13 13 13
VII.4.5.3. Simple Loops with Variable Step Size

Example: The following code for Linear Search elaborates this in

more detail.
 Once again, we can easily see that the code written in the
body of the loop has a complexity of .
 We now need to count the number of iterations.
Iteration 1 2 3 … … K+1

2 2 2 1 2 2
2 4
Search Size … …
VII.4.5.3. Simple Loops with Variable Step Size

Example: The following code for Linear Search elaborates this in

more detail.
 That is, after k+1 steps the loop will terminate.
 Since , by taking log base 2 of both sides we get .
 In general, when N cannot be written as power of 2, the number of
iterations will be given by the ceiling function .
 So, in the worst case, the number of iterations will be given by
.
 VII.4.5.4. A Deceptive Case

Before concluding this discussion on simple loops, let us look at a last, but
quite deceiving
Example: The following piece of code prints the table for number m.

for(int i=1; i<=10; i++)

number of
iterations
printf(“%d X %d = %d\n”, m, i, m*i);
is 10,
 VII.4.5.5. Nested Loop

For the purpose of this discussion, we can divide the nested loops
in two categories:
1. Independent loops: the number of iterations of the inner loop
are independent of any variable controlled in the outer loop.
2. Dependent loops: the number of iterations of the inner loop
are dependent upon some variable controlled in the outer loop.
 VII.4.5.5. Nested Loop (Independent Loops)

Let us consider the following code segment written to add two

matrices a, and b and store the result in matrix c.
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < COLS; j++) Nbr_It
Nbr_It
=
c[i][j] = a[i][j] + b[i][j]; =
ROWS
CLOS

 Total Number of iterations is ROWS COLS

 The time complexity of the algorithms is ROWS COLS .
 VII.4.5.5. Nested Loop (Independent Loops)

 In general, in the case of independent nested loops, all we

have to do is to determine the time complexity of each one of
these loops independent of the other and then multiply them to
get the overall time complexity.
 That is, if we have two independent nested loops with time
complexity of and , the overall time complexity of
the algorithm will be .
 VII.4.5.5. Nested Loop (Dependent Loops)

 When the number of iterations of the inner loop is

dependent upon some variable controlled in outer
loop, we need to do a little bit more to find out the time
complexity of the algorithm.
 What we need to do is to determine the number of
times the body of the inner loop will execute.
 VII.4.5.5. Nested Loop (Dependent Loops)

Example 1:
for (i = 0; i < N ; i++) {
min = i;
for (j = i; j < N; j++)
if (a[min] > a[j]) min = j;
swap(a[i], a[min]);
}

 As can be clearly seen, the value of j is dependent upon i, and hence the
number of iterations of the inner loop depend upon the value of i which
is controlled in the outer loop.
 VII.4.5.5. Nested Loop (Dependent Loops)

Example 1:
Value of i 0 1 2 … I … N-1

1 2 1
Number of
iterations of the … …
inner loop

1 2 ⋯ ⋯ 1
1
Total Number of

2
times the body of
the inner loop is
executed
 VII.4.5.5. Nested Loop (Dependent Loops)

Example 2:
for (i = 1; i < N; i++)
for (j = 1; j <= i; j = j * 2)
k++;

 The first thing to note here is that the inner loop follows a geometric
progression, going from 1 to i, with 2 as the common ratio between
consecutive terms.

 We have already seen that in such cases the number of iterations is given
by
 VII.4.5.5. Nested Loop (Dependent Loops)

Example 2:

Value of i 1 2 3 4 … N-1
Number of
iterations of the 1 log 2 2 log 3 2 log 4 3 log 5 … log

inner loop
Total Number of log 2 log 3 log 4 log 5 ⋯ log
log 2 3 4 5 ⋯ = log !
times the body

’
of the inner loop
is executed
 VII.4.5.5. Nested Loop (Dependent Loops)
Example 1: =
for (i = 0; i < N ; i++) {
min = i;
for (j = i; j < N; j++)
if (a[min] > a[j]) min = j;
swap(a[i], a[min]);
}
Example 2: =
for (i = 1; i < N; i++)
for (j = 1; j <= i; j = j * 2)
k++;
 VII.4.5.5. Nested Loop (Dependent Loops)

Example 3: =
for (i = 1; i < N; i = i*2)
for (j = 1; j < i; j++)
k++;

 Now, in this case, if we calculated the complexity of each loop

independently and then multiplied the results, we would get the time
complexity as ( log ).

 This is very different from what we get if we apply the approach used in
the previous examples.
 VII.4.5.5. Nested Loop (Dependent Loops)

Example 3:

2
Value of i 1 2 3 4 … N-1

iterations of the 1 2 2 2 4 2 8 2 ℎ
Number of
…
inner loop
Total Number of 2 2 2 2 ⋯ 2
2 1 2 2 1
times the body of
the inner loop is
executed
 VII.4.6. Non-Recursive Subprogram Call

 A non-recursive subprogram call is simply a statement

whose complexity is determined by the complexity
of the subprogram.
 Therefore, we simply determine the complexity of
the subprogram separately and then use that value in
our complexity derivations. The rest is as usual.
 VII.4.6. Non-Recursive Subprogram Call
Example 1:
float sum(float a[], int size) // assuming size > 0
{
float temp = 0;
for (int i = 0; i < size; i++)
=
temp = temp + a[i];
return temp;
}

 It is easy to see that this function has a linear time complexity, that is,
( ).
 VII.4.6. Non-Recursive Subprogram Call
Example 2:
float average(float data[], int size) // assuming size > 0
{
float total, mean;
total = sum(data, size);
mean = total/size;
return mean;
}

 It is easy to see that this function has a linear time complexity, that is,
( ).
 VII.4.6. Non-Recursive Subprogram Call
Example 3:
int foo(int n) {
int count = 0;
for (int j = 0; j < n; j++)
count++;
return count;
}

 It is easy to see that this function has a linear time complexity, that is,
( ).
 VII.4.6. Non-Recursive Subprogram Call
Example 4:
int bar(int n) {
temp = 0;
for (int i = 1; i < n; i = i * 2) {
temp1 = foo(i);
temp = temp1 + temp;
}
}

.
 It is easy to see that this function has a linear time complexity, that is,
 VII.4.6. Non-Recursive Subprogram Call
Example 5:
int factorial(int n){ //Returns a factorial of the natural n.
int fact = 1;
int i = 2;
while (i <= n){
fact = fact * i;
i = i + 1;
}
return fact;
}
 VII.5. Guidelines for Asymptotic Analysis of
Recursive Algorithms

 Determining the running time of a function that

calls itself recursively requires more work than
analyzing iterative (non-recursive) functions.
 A useful technique is to describe the execution
time using a recurrence relation.
 VII.5. Guidelines for Asymptotic Analysis of
Recursive Algorithms

A recurrence relation, also known as a

difference equation, is an equation that
defines a sequence recursively: each term
in the sequence is defined as a function
of the preceding terms.
 VII.5. Guidelines for Asymptotic Analysis of
Recursive Algorithms
To analyze the time complexity of a recursive function, you can follow these
steps:
 Determine the recurrence relation: Identify the recursive calls and their
respective inputs. Write an equation that expresses the time complexity of
the function in terms of its inputs.
 Solve the recurrence relation: Solve the equation to get a closed-form
solution for the time complexity.
 Analyze the solution: Determine the dominant term(s) in the closed-
form solution to get the time complexity of the function.
 VII.5.1. Recurrence Relation

 In the following sections, we will discuss methods that can be used to

find the time complexities of recursive algorithms.
 Previously, we defined the runtime of an algorithm as a function
of its input size . We will still do this when dealing with recursive
functions.
 However, because a recursive algorithm calls itself with a smaller input
size, we will write as a recurrence relation, or an equation that
defines the runtime of a problem in terms of the runtime of a
recursive call on smaller input.
 VII.5.1. Recurrence Relation

Example:
Compute the factorial function for an arbitrary non-

! ⋯ !
negative integer . Since

and ! by definition, we can compute .

with the following recursive algorithm.
 VII.5.1. Recurrence Relation

Example:
int Fact(int n) {
(1) if (n==0);
(2) return 1; /* basis */
else
(3) return n*Fact(n-1); /*induction */
}
 VII.5.1. Recurrence Relation

Example:
int Fact(int n) {
(1) if (n==0);
(2) return 1;
else
(3) return n*Fact(n-1);
}
 VII.5.1. Recurrence Relation

Example:
We can thus define by the following recurrence relation:
 VII.5.2. Solving Recurrence Relations

 After we convert a recursive algorithm into a recurrence

relation, we can use that recurrence relation to determine
its time complexity.
 There are many techniques for solving recurrence relations. In
this section, we will examine three methods:
 The iterative substitution method,
 The recurrence tree method,
 The master theorem
 1) Iterative Substitution Method
After we have a recurrence relation, the steps of the iterative
substitution method (also known as the iteration method) are as

,
follows:

,…, . , as their own recurrence relations and substitute

 Step 1: Write out the recursive terms

their equations into the original formula at each step.

 Step 2: Look for a pattern that describes at the step
(for any arbitrary ), and express it using a summation formula.
 1) Iterative Substitution Method
After we have a recurrence relation, the steps of the iterative
substitution method (also known as the iteration method) are as
follows:
 Step 3: Solve for such that the base case is the only recursive
term that is present on the right-hand side of the equation for
. Determine the closed form solution by replacing
instances of the base case with its value (e.g., replacing
with if the base case is ).
 1) Iterative Substitution Method
Example 1:

Consider the Recurrence:

 Solve the following recurrence relation using the

iterative substitution method ?
 1) Iterative Substitution Method
Example 1 (Solution):
From now on, we will substitute with the constant . This
simplifies our math without changing the result of our analysis.
 1) Iterative Substitution Method
Example 1 (Solution):
Now, let’s follow the procedure specified above.

⋮ ⋮ ⋮
 1) Iterative Substitution Method
Example 1 (Solution):
 To solve the generalized a last relation, we have to find the value
of . We note that , that is the number of operations
needed to raise a number to power needs just one
operation.
 We can reduce
⟹
to by setting
 1) Iterative Substitution Method
Example 1 (Solution):
 We can reduce
⟹
to by setting

 Substituting this value of in a last relation, we get

 Now we substitute the value of to get the solution.

 1) Iterative Substitution Method
Example 2:

Consider the Recurrence:

 Solve the following recurrence relation using the

iterative substitution method ?
 1) Iterative Substitution Method
Example 2 (Solution):

⋮ ⋮ ⋮
. ;
 1) Iterative Substitution Method
Example 2 (Solution):
 The maximum value of (then only we get )

. .
.
 1) Iterative Substitution Method
Note: If you want to write a recurrence relation for , you must
replace ALL instances of with , even the terms outside the recursive
call! A common mistake is only substituting the in the recursive term.
Example 3:

 Correct:
 Incorrect:
 2) Recurrence Tree Method
 While the substitution method works well for many
recurrence relations, it is not an appropriate technique
when recurrence relation model algorithms are based on
the “divide and conquer” paradigm.
 The recurrence tree method is a popular technique for
solving such recurrence relations, particularly for
solving unbalanced recurrence relations.
 2) Recurrence Tree Method
 In the recursion method, we draw a recurrence tree and calculate
the time taken at each level of the tree.
 Finally, we sum the costs within each of the levels of the tree to
obtain a set of pre-level costs and then sum all pre-level costs to
determine the total cost of all levels of the recursion.
 To draw the recurrence tree, we start from the given recurrence
and keep drawing until we find a pattern among levels. This
pattern is usually an arithmetic or geometric series.
 2) Recurrence Tree Method
Given a recurrence relation, we can build a recursion tree
by repeating the following steps until we reach the base
case:
 At each level, each node is assigned the total amount of
work that is done outside the recursive call(s).
 Each recursive call creates a branch to the next level of
the tree.
 2) Recurrence Tree Method
Example:
Consider the following recurrence relation :

 This recurrence relation calls itself four times with half

the input size and does an additional work.
 With a recursion tree approach, we can visualize the
first recursive call as follows
 2) Recurrence Tree Method
Example:
Consider the following recurrence relation :
 2) Recurrence Tree Method
Example:
How much work do these recursive calls to do?
 We know from our recurrence relation that
, where a recursive call with an input
size of does work and makes two recursive calls, each
with input size .
 We can use this to extend our tree down another level.
 2) Recurrence Tree Method
Example:
Level Recursion Tree for Work
2) Recurrence Tree Method
Example:

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

⋯⋯⋯ ⋯⋯⋯⋯⋯ ⋯⋯⋯⋯ ⋯⋯⋯

 2) Recurrence Tree Method
Example:
⋯
⋯
∑
 2) Recurrence Tree Method
Summary:

 Let is defined by the recurrence relation :

 where and are constants and

is an asymptotically positive function.
 2) Recurrence Tree Method
Summary:
We conclude our work with these affirmations:
 Number of nodes at level :
 Input Size at level :
 Height of tree:
 Number of levels:
 Cost at level : .

 Total complexity : . ∑
 3) Master Theorem Method
The master method provides a “cookbook” method for
solving recurrences of the form

where and are constants and is an

asymptotically positive function (Asymptotically positive
means that the function is positive for all sufficiently large ).
 3) Master Theorem Method

 is the size of the problem.

 is the number of sub-problems in the recursion.
 is the size of each sub-problem. (Here, it is assumed that all
sub-problems are essentially the same size.)
 is the sum of the work done outside the recursive calls,
which includes the cost of decomposing the problem and
recomposing the results.
 3) Master Theorem Method
Theorem I.1 (Master theorem)
If the recurrence relation of an algorithm is of the form:

where , , and is an asymptotically positive function that is

, then the following is true:
• Case 1: If , the complexity of .
• Case 2: If , the complexity of .
• Case 3: If , the complexity of .
 3) Master Theorem Method
Theorem I.1 (Master theorem)
If the recurrence relation of an algorithm is of the form:

where , , and is an asymptotically positive function that is

, then the following is true:
More formally,
 3) Master Theorem Method
Notes:
 There must exist a base case that is solvable in constant time.
 The value represents the number of times a recursive call is made,
 The value represents the factor that the input is divided by with each
recursive call,
 The value represents the highest power of the polynomial term .
 The values of and are independent of .
 The Master Theorem can only be used if all these conditions are met.
 3) Master Theorem Method
Summary:
The steps for using the Master Theorem are as follows:
1) Determine the values of , , and .
2) Make sure that the Master Theorem can be used on the
recurrence relation.
 3) Master Theorem Method
Summary:
2) Make sure that the Master Theorem can be used on the recurrence
relation.
 The coefficient of the recursive call, , must be at least one .
 The argument of the recursive call must be divided by some number,
, that is larger than one .
 The function must be an asymptotically positive function with
complexity .
 There exists a base case that can be solved in constant time
e.g., .
 3) Master Theorem Method
Summary:
The steps for using the Master Theorem are as follows:
1) Determine the values of , , and .
2) Make sure that the Master Theorem can be used on the
recurrence relation.
3) Compare the values of a and to determine which
case of the Master Theorem should be used.
 3) Master Theorem Method
Example 1:
Consider the following recurrence relation :

 Solve the recurrence by using the master

theorem?
 3) Master Theorem Method
Example 1 (Solution):
 For this recurrence, we have
, , and ⟹
 Since ,
 As per of the master theorem, the solution is :
 3) Master Theorem Method
Example 2:
Consider the following recurrence relation :

 Solve the recurrence by using the master

theorem?
 3) Master Theorem Method
Example 2 (Solution):
 For this recurrence, we have
, , and ⟹
 Since ,
 As per of the master theorem, the solution is :
 3) Master Theorem Method
Example 3:
Consider the following recurrence relation :

 Solve the recurrence by using the master

theorem?
 3) Master Theorem Method
Example 3 (Solution):
 For this recurrence, we have
, , and ⟹
 Since ,
 As per of the master theorem, the solution is :
 3) Master Theorem Method
Example 4:
Consider the following recurrence relation :

 Solve the recurrence by using the master

theorem?
 3) Master Theorem Method
Example 4 (Solution):
 For this recurrence, we have
, , and
 Does not satisfy either Case 1 or 2 or 3 of the Master’s
theorem.
 Here, the master theorem does not apply.
 a) The Extended Master Theorem for
Polylogarithmic Functions
 There is actually an extension of the Master Theorem that can
be used if is a polylogarithmic function, but you will not
need to know this for the class.
 Given a recurrence relation of the form
,

where is of the form , the following

are true:
 a) The Extended Master Theorem for
Polylogarithmic Functions
Extended Master theorem
• Case 1: If , then .
• Case 2: If , then
 If , then .
 If , then .
 If , then .

0, then
• Case 3: If , then

0, then
 If .
 If .
 a) The Extended Master Theorem for
Polylogarithmic Functions

Example 1:
Consider the following recurrence relation :

 Solve the recurrence by using the master theorem

or the extended master theorem?
 a) The Extended Master Theorem for
Polylogarithmic Functions

Example 1 (Solution):
 Here, the master theorem does not apply, but rather we apply
the extended master theorem.

, , and ⟹ &
 For this recurrence, we have

 Since ,
 As per of the extended master theorem, the solution is :
 a) The Extended Master Theorem for
Polylogarithmic Functions

Example 2:
Consider the following recurrence relation :

 Solve the recurrence by using the master theorem

or the extended master theorem?
 a) The Extended Master Theorem for
Polylogarithmic Functions

Example 2 (Solution):
 Here, the master theorem does not apply, but rather we apply the extended
master theorem.

, , and ⟹ &
 For this recurrence, we have

,
⟹
 Since
 As per of the extended master theorem, , the
solution is :
 Exercise

Consider the following recurrence relation :

 Solve the following recurrence relation ?

 Exercise

Consider the following recurrence relation :

Exercise
Level Recursion Tree for Work
Exercise

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

⋯⋯⋯ ⋯⋯⋯⋯⋯ ⋯⋯⋯⋯ ⋯⋯⋯

 Exercise

/
Questions ?