University of M’sila Department of Computer Science

Module: Data Structures and Algorithms 3 2nd Year License (2L)

CHAPTER 1 : Algorithm Analysis (2024-2025)

CHAPTER 1
Algorithm Analysis
I.1. Introduction
This chapter focuses on the analysis of execution time as well as the smooth running of algorithms.
Analysis of an algorithm is the same thing as estimating the efficiency of the algorithm. There are
two fundamental parameters based on which we can analyze the algorithm and they are Space and
Time Complexity. There is also the concept in time complexity of estimating the running time of
an algorithm and we have the Worst-case, Average-case, and Best-case. We will introduce several
tools to accomplish such an analysis: asymptotic notation (O, Θ, Ω). These notions will be
accompanied by examples.

I.2. 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.
Data structure can be classified into two categories:
1) Primitive data structures consist of the numbers and the characters which are built in
programs. These can be manipulated or operated directly by the machine level instructions.
Basic data types such as integer, real, character, and Boolean come under primitive data
structures. These data types are also known as simple data types because they consist of
characters that cannot be divided.
2) Non-primitive data structures are those that are derived from primitive data structures.
These data structures cannot be operated or manipulated directly by the machine level
instructions. They focus on formation of a set of data elements that is either homogeneous
(same data type) or heterogeneous (different data type).
These are further divided into linear and non-linear data structure based on the structure
and arrangement of data.

• Linear data structures: Elements are accessed in a sequential order but it is not
compulsory to store all elements sequentially (say, Linked Lists). Examples: Linked
Lists, Stacks and Queues.

• Non-linear data structures: Elements of this data structure are stored/accessed

in a non-linear order. Examples: Trees and graphs.
The following figure (Figure 1.1) shows the different classifications of Data Structures.

Dr. Dabba Ali 1/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

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
Figure 1.1 : Classifications of Data Structures.
I.3. 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.

I.3.1. Characteristics of Algorithms

The main Characteristics or features of Algorithms are:

• Input: Algorithms take zero or more inputs and produce at least one output based on these
inputs.
• Output: Every algorithm should produce a result; it can be a value, a set of values, a
decision, or some other form of output.
• Definiteness: Algorithms should have clear and unambiguous instructions for each step.
Each step should be precisely defined and executable.
• Finiteness: An algorithm should terminate after executing a finite number of steps. It
should not run indefinitely or enter an infinite loop.
• Feasible: The algorithm must be simple, generic, and practical, such that it can be executed
with the available resources. It must not contain some future technology or anything.
• Effectiveness: Algorithms should be practical and feasible. They should be able to be
executed within the constraints of time and space available.
• Language Independent: The Algorithm designed must be language independent, i.e., it
must be just plain instructions that can be implemented in any language, and yet the output
will be the same, as expected.
I.3.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.

Dr. Dabba Ali 2/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

• Scalability: Good algorithms can handle varying input sizes without a significant increase
in resources.
I.3.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.

I.4. 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.
We will be looking more at time rather than space because time is instead a more limiting parameter
in terms of the hardware. It is not easy to take a computer and change its speed. So, if we run an
algorithm on a particular platform, we are more or less stuck with the performance the platform
can give us in terms of speed.

I.4.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.

I.4.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 𝒙. The execution time of 𝓐 in the worst case is the function
𝑻𝒎𝒂𝒙 ∶ ℕ → ℕ such that:

𝑻𝒎𝒂𝒙 (𝒏) = 𝑴𝒂𝒙{𝒇(𝒙): 𝒊𝒏𝒑𝒖𝒕 𝒙 𝒐𝒇 𝒔𝒊𝒛𝒆 𝒏}.

In other words, 𝑻(𝒏) indicates the largest number of operations performed among all inputs of
size 𝒏.

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.

Dr. Dabba Ali 3/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

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, Assignment n 2n

return s;} 0 / - 0

Total T(n)= 6n+3

Intuitively, then, Algorithm (function) works in linear time concerning n, i.e., whatever the input,
the execution time is approximately n except for certain constants.

I.4.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:

𝑻𝒎𝒂𝒙 (𝒏𝟏 , 𝒏𝟐 , . . . , 𝒏𝒌 ) = 𝑴𝒂𝒙{𝒇(𝒙): 𝒊𝒏𝒑𝒖𝒕 𝒙 𝒐𝒇 𝒔𝒊𝒛𝒆 (𝒏𝟏 , 𝒏𝟐 , . . . , 𝒏𝒌 )}.

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.

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

I.4.2. Types of Time Complexity Analysis

We have three types of analysis related to time complexity, which are:

1) 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.

Dr. Dabba Ali 4/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
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.
2) 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.
3) 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.

I.5. 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.

𝑶(𝒇) notation represents the complexity of an algorithm, which is also termed an Asymptotic
notation or "Big O" notation. Here, the 𝒇 corresponds to the function whose size is the same as
that of the input data. The complexity of the asymptotic computation 𝑶(𝒇) determines in which
order the resources such as CPU time, memory, etc. are consumed by the algorithm that is
articulated as a function of the size of the input data.

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".

I.6. 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.

I.6.1. Asymptotic Notations

A problem may have various algorithmic solutions. In order to choose the best algorithm for a
particular process, you must be able to judge the time taken to run a particular solution. More
precisely, you must be able to judge the time it takes to run two solutions and choose the best one.
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. It can generally be represented as the fastest
possible, the slowest possible or the average possible.
The notations such as O (Big-O), Θ (Theta), and Ω (Omega) are called as asymptotic notations.
These are the mathematical notations that are used in three different cases of time complexity.

Dr. Dabba Ali 5/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
Since Big-O notation gives the worst-case running time of an algorithm, it is widely used to
analyze an algorithm as we are always interested in the worst-case scenario. Therefore, in this
course, we'll focus on the Big-O notation.

I.6.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).

Definition I.1
We consider functions from ℕ to ℝ that are eventually positive, i.e., functions belonging to:
ℱ = {𝑓: ℕ → ℝ ∶ ∃ 𝑚 ∈ ℕ, ∀𝑛 ≥ 𝑚 𝑓(𝑛) > 0}
Let 𝑔 ∈ ℱ. The set 𝓞(𝒈) is defined by:
𝒪(𝑔) = {𝑓 ∈ ℱ: ∃ 𝑐 ∈ ℝ + , ∃ 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 𝑓(𝑛) ≤ 𝑐. 𝑔(𝑛)}
➢ Intuitively, 𝒇 ∈ 𝓞(𝒈) indicates that 𝒇 increases as quickly or less quickly than the
function 𝒈.
➢ We call the values c and 𝒏𝟎 a multiplicative constant and a threshold.
The graphical representation of f(n) = O(g(n)) is shown in figure 1.2, where the running time
increases considerably when n increases.

Rate of Growth

Input Size

Figure 1.2: Big O Notation f(n) = O(g(n))

Example:

Consider the function 𝒇(𝒏) = 𝟓𝒏𝟐 + 𝟒𝟎𝟎𝒏 + 𝟗

The function 𝒇 is greater than 𝒈(𝒏) = 𝒏𝟐

However, we can show that 𝒇 ∈ 𝓞(𝒏𝟐 ). We have :

𝐟(𝐧) = 𝟓𝐧𝟐 + 𝟒𝟎𝟎𝐧 + 𝟗

≤ 𝟓𝒏𝟐 + 𝟒𝟎𝟎𝒏 + 𝒏𝟐 for all 𝒏 ≥ 𝟑

≤ 𝟓𝒏𝟐 + 𝒏. 𝒏 + 𝒏𝟐 for all 𝒏 ≥ 𝟒𝟎𝟎

= 𝟕𝒏𝟐
Thus, taking 𝐜 = 𝟕 as a multiplicative constant and 𝒏𝟎 = 𝟒𝟎𝟎 as a threshold, we conclude that
𝒇 ∈ 𝓞(𝒏𝟐 ).

Dr. Dabba Ali 6/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

I.6.1.2. Big-O Notation for Complexity Class

The most common complexity classes (in increasing order) are the following:

• 𝓞(𝟏) pronounced ‘Oh of one’, or constant complexity;

• 𝓞(𝒍𝒐𝒈𝟐 𝒍𝒐𝒈𝟐 𝒏) ‘Oh of log log en’;
• 𝓞(𝒍𝒐𝒈𝟐 𝒏) ‘Oh of log en’, or logarithmic complexity;
• 𝓞(𝒏) ‘Oh of en’, or linear complexity;
• 𝓞(𝒏𝒍𝒐𝒈𝟐 𝒏) ‘Oh of en log en’;
• 𝓞(𝒏𝟐 ) ‘Oh of en squared’, or quadratic complexity;
• 𝓞(𝒏𝟑 ) ‘Oh of en cubed’, or cubic complexity;
• 𝓞(𝟐𝒏 ) ‘Oh of two to the en’, or exponential complexity.
• 𝓞(𝒏!) ‘Oh of en factorial’, or factorial complexity.

As a representative, we choose the function which gives the class its name e.g., for 𝓞(𝒏) we choose
the function 𝒇(𝒏) = 𝒏, for 𝓞(𝒍𝒐𝒈𝟐 𝒏) we choose 𝒇(𝒏) = 𝒍𝒐𝒈𝟐 𝒏, and so on. Let’s assume we
have algorithms with these functions describing their complexity. Table 1.1 lists how many
operations it will take them to deal with a problem of a given size:
𝒇(𝒏) 𝒏=𝟒 𝒏 = 𝟏𝟔 𝒏 = 𝟐𝟓𝟔 𝒏 = 𝟏𝟎𝟐𝟒 𝒏 = 𝟏𝟎𝟒𝟖𝟓𝟕𝟔
1 1 1 1 𝟏. 𝟎𝟎 × 𝟏𝟎𝟎 𝟏. 𝟎𝟎 × 𝟏𝟎𝟎
𝒍𝒐𝒈𝟐 𝒍𝒐𝒈𝟐 𝒏 1 2 3 𝟑. 𝟑𝟐 × 𝟏𝟎𝟎 𝟒. 𝟑𝟐 × 𝟏𝟎𝟎
𝒍𝒐𝒈𝟐 𝒏 2 4 8 𝟏. 𝟎𝟎 × 𝟏𝟎𝟏 𝟐. 𝟎𝟎 × 𝟏𝟎𝟏
𝒏 4 16 𝟐. 𝟓𝟔 × 𝟏𝟎𝟐 𝟏. 𝟎𝟐 × 𝟏𝟎𝟑 𝟏. 𝟎𝟓 × 𝟏𝟎𝟔
𝒏𝒍𝒐𝒈𝟐 𝒏 8 64 𝟐. 𝟎𝟓 × 𝟏𝟎𝟑 𝟏. 𝟎𝟐 × 𝟏𝟎𝟒 𝟐. 𝟏𝟎 × 𝟏𝟎𝟕
𝒏𝟐 16 256 𝟔. 𝟓𝟓 × 𝟏𝟎𝟒 𝟏. 𝟎𝟓 × 𝟏𝟎𝟔 𝟏. 𝟏𝟎 × 𝟏𝟎𝟏𝟐
𝒏𝟑 64 4096 𝟏. 𝟔𝟖 × 𝟏𝟎 𝟕
𝟏. 𝟎𝟕 × 𝟏𝟎𝟗 𝟏. 𝟏𝟓 × 𝟏𝟎𝟏𝟖
𝟐𝒏 16 65536 𝟏. 𝟏𝟔 × 𝟏𝟎𝟕𝟕 𝟏. 𝟖𝟎 × 𝟏𝟎𝟑𝟎𝟖 𝟔. 𝟕𝟒 × 𝟏𝟎𝟑𝟏𝟓𝟔𝟓𝟐
Table 1.1: Number of operations.
Some of these numbers are so large that it is rather difficult to imagine just how long a time span
they describe. Hence, Table 1.2 gives time spans rather than instruction counts, based on the
assumption that we have a computer which can operate at a speed of 1 MIPS (MIPS : a million
instructions per second):
𝒇(𝒏) 𝒏=𝟒 𝒏 = 𝟏𝟔 𝒏 = 𝟐𝟓𝟔 𝒏 = 𝟏𝟎𝟐𝟒 𝒏 = 𝟏𝟎𝟒𝟖𝟓𝟕𝟔
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 𝟐. 𝟓𝟔 sec 𝟏. 𝟎𝟐 msec 𝟏. 𝟎𝟓 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
Table 1.2: Time spent.
It is clear that, as the sizes of the problems get really big, there can be huge differences in the time
it takes to run algorithms from different complexity classes. For algorithms with exponential

Dr. Dabba Ali 7/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

complexity, 𝑶(𝟐𝒏 ), even modest-sized problems have run times that are greater than the age of
the universe (about 1,4 × 1010 years), and current computers rarely run uninterrupted for more
than a few years. This is why complexity classes are so important they tell us how feasible it is likely
to be to run a program with a particularly large number of data items. Typically, people do not
worry much about complexity for sizes below 10, or maybe 20, but the above numbers make it
clear why it is worth thinking about complexity classes where bigger applications are concerned.

I.6.1.3. Properties of Asymptotic Notations

To understand the concept of asymptotic notations fully, let us look at some of the general
properties of asymptotic notations.

a) General (Constant Factor)

If 𝒇(𝒏) = 𝓞(𝒈(𝒏)) 𝒕𝒉𝒆𝒏 𝒂 × 𝒇(𝒏) = 𝓞(𝒈(𝒏))

e.g., 𝒇(𝒏) = 𝟐𝒏𝟐 + 𝟓 𝒊𝒔 𝓞(𝒏𝟐 ), 𝒕𝒉𝒆𝒏 𝟒 × 𝒇(𝒏) = 𝟖𝒏𝟐 + 𝟐𝟎 𝒊𝒔 𝒂𝒍𝒔𝒐 𝓞(𝒏𝟐 )

b) Reflexive

Given 𝒇(𝒏), 𝒕𝒉𝒆𝒏 𝒇(𝒏) = 𝓞(𝒇(𝒏)) , since maximum value of 𝒇(𝒏) will be 𝒇(𝒏) itself, i.e., every
function is an upper-bound of itself.

e.g., 𝒇(𝒏) = 𝒏𝟐 = 𝓞(𝒏𝟐 )

c) Transitive

If 𝒇(𝒏) = 𝓞(𝒈(𝒏)) 𝑎𝑛𝑑 𝒈(𝒏) = 𝓞(𝒉(𝒏)), 𝒕𝒉𝒆𝒏 𝒇(𝒏) = 𝓞(𝒉(𝒏))

e.g., 𝒇(𝒏) = 𝒏, 𝒈(𝒏) = 𝒏𝟐 , 𝑎𝑛𝑑 𝒉(𝒏) = 𝒏𝟑

here, 𝒇(𝒏) = 𝓞(𝒏𝟐 ) & 𝒈(𝒏) = 𝓞(𝒏𝟑 ) ⟹ 𝒇(𝒏) = 𝓞(𝒏𝟑 ) 𝒐𝒓 𝓞(𝒉(𝒏))

I.6.1.4. Limitations of Big-O Notation

Big-O notation has certain limitations when it comes to expressing the complexity of algorithms.
These limitations are as follows:

• 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. this is an important
consideration.

I.7. 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. Thus, we throw away leading
constants. We will also throw away lower-order terms, so what we are essentially doing is

Dr. Dabba Ali 8/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
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. The program may stop earlier than this, but
never later.

I.7.1. Assumptions in Complexity Analysis

Calculating the complexity of an algorithm is based on the following assumptions:

• 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.
• 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.

I.7.2. Simplification Rules

In algorithm analysis, particularly when using Big-O notation, there are simplification rules that are
commonly employed to analyze the time and space complexity of algorithms. Here are some
common simplification rules used in complexity analysis:

• 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 𝓞(𝒏𝟑 ) + 𝓞(𝒏) = 𝓞(𝒏𝟑 + 𝒏) = 𝓞(𝒏𝟑 ).
• 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.

I.7.3. How to Calculate the Approximate Time Kaken 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.

Dr. Dabba Ali 9/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

• Recursive Algorithm: The function calls itself until the condition is met in the recursive
approach. It integrates the branching structure.

I.7.4. Guidelines for Asymptotic Analysis of Iterative Algorithms

There are some general rules to help us determine the running time of iterative algorithms

I.7.4.1. Simple Statement and O(1)

For the purpose of this discussion, 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. 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).

I.7.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 𝓞(𝟏).

I.7.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. As an example, consider the following sequence of statements:
statement1 // 𝓞(𝒏𝟐 )

statement2 // 𝓞(𝟏)

statement3 // 𝓞(𝒏)

statement4 // 𝓞(𝒏)

The time complexity of the sequence will be:

𝓞(𝒏𝟐 ) + 𝓞(𝟏) + 𝓞(𝒏) + 𝓞(𝒏) = 𝑴𝒂𝒙 (𝓞(𝒏𝟐 ) + 𝓞(𝟏) + 𝓞(𝒏) + 𝓞(𝒏)) = 𝓞(𝒏𝟐 )

I.7.4.4. Selection

A selection can have many branches and can be implemented with the help of 𝑖𝑓 or 𝑠𝑤𝑖𝑡ch
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. As has already
been mentioned, Big O provides us growth rate in the worst-case scenario. 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. Hence the Big O for an 𝑖𝑓 or a 𝑠𝑤𝑖𝑡𝑐h
statement would be equal to the maximum of the Big O of its individual branches. As an example,
consider the following code segment:

Dr. Dabba Ali 10/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
if (cond1) statement1 // 𝓞(𝒏𝟐 )

else if (cond2) statement2 // 𝓞(𝟏)

else if (cond3) statement3 // 𝓞(𝒏)

else statement4 // 𝓞(𝒏 𝒍𝒐𝒈 𝒏)

The time complexity of this code segment will be:

𝑴𝒂𝒙 (𝓞(𝒏𝟐 ) + 𝓞(𝟏) + 𝓞(𝒏) + 𝓞(𝒏 𝒍𝒐𝒈 𝒏)) = 𝓞(𝒏𝟐 )

I.7.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.

I.7.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: 𝓞(𝒇(𝒏)) . 𝓞(𝒇(𝒏)) = 𝓞(𝒇(𝒏). 𝒈(𝒏))

Example:
for( i = 1; i <= n; i ++)
number of iterations is n, 𝓞(𝒏)
S = S + 2; // constants time, 𝓞(𝟏)

Total time = 𝓞(𝟏) × 𝓞(𝒏) = 𝓞(𝟏 × 𝒏) = 𝓞(𝒏) .

Simple loops come in many different varieties. The most common ones are the counting loops
with uniform step size and loops where the step size is multiplied or divided by a fixed number.
These are discussed in the following subsections.

I.7.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.

Example: The following code for Linear Search elaborates this in more detail.

index = -1; // 𝓞(𝟏)

Dr. Dabba Ali 11/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
for (int i = 0; i < N; i++)

if (a[i] == key) {
number of iterations is n, 𝓞(𝒏)
index = i; // 𝓞(𝟏)

break; // 𝓞(𝟏)
} //for
We can easily see that:

1. Time complexity of the code in the body of the loop is 𝓞(𝟏)

2. In the worst case (when key is not found), there will be 𝒏 iterations of the for loop, resulting
in 𝓞(𝒏).
3. Therefore, the time complexity of the Linear Search algorithms is: 𝓞(𝟏) × 𝓞(𝒏) = 𝓞(𝒏).
I.7.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.
As an example, let us consider the following code for the Binary Search Algorithm:
high = N-1;
low = 0;
index = -1;
while(high >= low)
{
mid = (high + low)/2;
if (key == a[mid]) { index = mid; break;}
else if (key > a[mid]) low = mid + 1;
else high = mid – 1;
}
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.
For the sake of simplicity, let us assume that N is a power of 2. That is, we can write 𝑵 = 𝟐𝒌 where
k is a non-negative integer. Once again, the worst case will occur if the key is not found. In each
iteration, the search space spans from low to high. So, in the first iteration we have N elements in
this range. After the first iteration, the range is halved as either the low or the high is moved to
mid + 1 or mid - 1 respectively, effectively reducing the search space to approximately half the
original size. This pattern continues until we either find the key or the condition high >= low is
false, which is the worst-case scenario. This pattern is captured in this Table 1.3.
Iteration 1 2 3 … … … K+1
𝑁 𝑁
Search Size 𝑁 = 2𝑘 = 2𝑘−1 = 2𝑘−2 … … … 1 = 2𝑘−𝑘 = 20
2 4
Table 1.3: The number of iterations in binary search

Dr. Dabba Ali 12/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

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 𝓞([𝒍𝒐𝒈𝟐 𝑵]). 𝑻𝒐𝒕𝒂𝒍 𝒕𝒊𝒎𝒆 𝑻(𝒏) = 𝓞(𝟏) × 𝓞(𝒍𝒐𝒈 𝒏) = 𝓞(𝒍𝒐𝒈 𝒏)

I.7.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++)

printf(“%d X %d = %d\n”, m, i, m*i);

This looks like an algorithm with time complexity 𝓞(𝑵) . However, since the number of iterations
is fixed, hence it is not dependent upon any input data size and therefore it will always take the
same amount of time. Therefore, its time complexity is 𝓞(𝟏).

I.7.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.
a) 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++)

c[i][j] = a[i][j] + b[i][j];

For each iteration of the outer loop, the inner loop will iterate COLS number of times and is
independent of any variable controlled in the outer loop. Since the outer loop iterates ROWS
number of times, the statement in the body of the inner loop will be executed ROWS x COLS
number of times. Hence the time complexity of the algorithms is 𝓞(𝐑𝐎𝐖𝐒 × 𝐂𝐎𝐋𝐒 ).
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 𝓞(𝐱) × 𝓞(𝐲) = 𝓞(𝐱 × 𝐲).

b) 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.

Dr. Dabba Ali 13/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
As an example, consider the following algorithm:
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. In order to analyze
such cases, we can use a table like the one given in Table 1.4.

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

Number of iterations
𝑁 𝑁−1 𝑁−2 … 𝑁−𝑖 … 1
of the inner loop
𝑇(𝑁) = 𝑁 + (𝑁 − 1) + (𝑁 − 2) + ⋯ + (𝑁 − 𝑖) + ⋯ + 1
Total Number of
𝑁(𝑁 + 1)
times the body of the =
2
inner loop is executed
= 𝓞(𝑵𝟐 )
Table 1.4: Analysis of the algorithm.
As shown in the table, the time complexity of algorithm is thus 𝓞(𝑵𝟐 ).
Let us look at another interesting example.
k = 0;
for (i = 1; i < N; i++)
for (j = 1; j <= i; j = j * 2)
k++;

Once again, the number of iterations in the inner loop depend upon that value of i which is
controlled by the outer loop. Hence it is a case of dependent loops. Let us now use the same
technique to find the time complexity of this algorithm. 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
[𝒍𝒐𝒈𝟐 (𝒊 + 𝟏)]. Using this information, the time complexity is calculated as shown in Table 1.5.
Value of i 1 2 3 4 … N-1
Number of iterations 1 2 2 3
… [log(𝑁)]
of the inner loop = [log(2)] = [log(3)] = [log(4)] = [log(5)]

𝑇(𝑁) = log 2 + log 3 + log 4 + log 5 + ⋯ + log 𝑁

Total Number of
times the body of the = log(2 × 3 × 4 × 5 × … × 𝑁) = log(𝑁!)
inner loop is executed
= 𝓞(𝑵 𝒍𝒐𝒈 𝑵) 𝑏𝑦 𝑆𝑡𝑖𝑟𝑙𝑖𝑛𝑔’𝑠 𝑓𝑜𝑟𝑚𝑢𝑙𝑎
Table 1.5: Analysis of a first program involving nested dependent loop

Dr. Dabba Ali 14/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
Analyses of both the algorithms discussed above are a little deceiving. It appears that in both these
cases we can get the right answer by simply finding the complexity of each loop independently and
then multiplying them just like we did in the case of independent loops. Hence this whole exercise
seems to be an overkill. Although this statement is true to the extent that we will indeed get the
same answer, however, this is not the right approach and will not always give the right answer in
such cases. To understand why, let us consider the following code:
for (int i = 1; i < N; i = i * 2)

for (int j = 0; 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. The analysis is shown in Table 1.6.

Value of i 1 2 3 4 … N-1

Number of 𝑁 ≈ 2𝑘
iterations of the 1 = 20 2 = 21 4 = 22 8 = 23 … 𝑊ℎ𝑒𝑟𝑒
inner loop
𝑘 = [𝑙𝑜𝑔𝑁]
Total Number of 𝑇(𝑁) = 20 + 21 + 22 + 23 + ⋯ + 2𝑘
times the body
= 2𝑘+1 − 1 = 2 × 2𝑘 − 1
of the inner loop
is executed = 𝓞(𝟐𝒌 ) = 𝓞(𝑵)

Table 1.6: Analysis of a second program involving nested dependent loop

I.7.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.
For example, let us consider the following program:
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, 𝑂(𝑁).
Let us now use it to determine the time complexity of the following function:

Dr. Dabba Ali 15/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
float average(float data[], int size) // assuming size > 0

float total, mean ;

total = sum(data, size); //O(N)

mean = total/size; //O(1)

return mean; //O(1)

We first determine the time complexity of each statement. Then we determine the complexity of
the entire function by simply using the method discussed earlier to determine the complexity of a
sequence of statements. This gives us the time complexity of O(n) for the function.
It is important to remember that if we have a function call inside the body of a loop, we need to
apply the guidelines for the loops. In that case we need to carefully examine the situation as
sometimes the time taken by the function call is dependent upon a variable controlled outside the
function and hence gives rise to a situation just like dependent loops discussed above. In such
cases, the complexity is determined with the help of techniques similar to the one used in the case
of dependent loops.
As an example, consider the following example:
int foo(int n) {

int count = 0;

for (int j = 0; j < n; j++)

count++;

return count;

}
As can be easily seen, if considered independently, this function has linear time complexity, i.e., it
is 𝑂(𝑁). Let us now use it inside another function:
int bar(int n) {

temp = 0;

for (int i = 1; i < n; i = i * 2)

temp1 = foo(i);

temp = temp1 + temp;

If we are not careful, we can be easily deceived by it. If we treat it casually, we can put the
complexity of the for loop to be 𝑂(log 𝑁) and we have already determined that the complexity of
the function foo is 𝑂(𝑁). Hence, the overall complexity would be calculated to be 𝑂(𝑁log 𝑁).
However, a more careful analysis would show that 𝑂(𝑁) is a tighter upper bound for this function

Dr. Dabba Ali 16/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
and that should be used to describe the complexity of this function. The detailed analysis of this
problem is left as an exercise for the students.

Example: Let's calculate the complexity of the following algorithm (n! : factorial of n) :
int factorial(int n) {

// Returns the factorial of the natural n.

int fact = 1; 𝒊𝒏𝒊𝒕𝒊𝒂𝒍𝒊𝒛𝒂𝒕𝒊𝒐𝒏: 𝓞(𝟏)

int i = 2; 𝒊𝒏𝒊𝒕𝒊𝒂𝒍𝒊𝒛𝒂𝒕𝒊𝒐𝒏: 𝓞(𝟏)

while (i <= n){ 𝒕𝒆𝒔𝒕 𝒊𝒏 ∶ 𝓞(𝟏)

𝒏−𝟏
fact = fact * i; 𝒎𝒖𝒍𝒕𝒊𝒑𝒍𝒊𝒄𝒂𝒕𝒊𝒐𝒏 𝒂𝒏𝒅 𝒂𝒔𝒔𝒊𝒈𝒏𝒎𝒆𝒏𝒕: 𝑶(𝟏) 𝒊𝒕𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔:
𝓞(𝒏)
i = i + 1; 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒂𝒏𝒅 𝒂𝒔𝒔𝒊𝒈𝒏𝒎𝒆𝒏𝒕: 𝓞(𝟏)

return fact; 𝒓𝒆𝒕𝒖𝒓𝒏: 𝓞(𝟏)

According to the rules seen above, the complexity is: 𝓞(𝟏) + 𝓞(𝒏) × 𝓞(𝟏) + 𝓞(𝟏) = 𝓞(𝒏)

I.7.5. Guidelines for Asymptotic Analysis of Recursive Algorithms

In this section, we will see how to apply the general framework for analysis of algorithms to
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. 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.
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.
I.7.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.

Dr. Dabba Ali 17/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

Example:

Compute the factorial function 𝑭(𝒏) = 𝒏 for an arbitrary nonnegative integer 𝒏. Since

𝒏! = 𝟏 × 𝟐 × … × (𝒏 − 𝟏) × 𝒏 = 𝒏(𝒏 − 𝟏)! 𝒇𝒐𝒓 𝒏 ≥ 𝟏

and 𝟎! = 𝟏by definition, we can compute 𝑭(𝒏) = 𝑭(𝒏 − 𝟏). 𝒏 with the following recursive
algorithm.
int Fact(int n) {

(1) if (n==0);

(2) return 1; /* basis */

else

(3) return n * Fact(n-1); /* induction */

Since there is only one function, fact, involved, we shall use 𝑻(𝒏) for the unknown running time
of this function. We shall use 𝒏, the value of the argument, as the size of the argument. Clearly,
recursive calls made by fact when the argument is 𝒏 have a smaller argument, (𝒏 − 𝟏) to be precise.

For the basis of the inductive definition of 𝑻(𝒏) we shall take 𝒏 = 𝟎, since no recursive call is
made by fact when its argument is 𝟎. With 𝒏 = 𝟎, the condition of line (𝟏) is true, and so the call
to fact executes lines (𝟏) and (𝟏). Each takes constant 𝒂 time i.e., 𝓞(𝟏) time, and so the running
time of 𝑭𝒂𝒄𝒕 in the basis case is 𝒂 time i.e., 𝓞(𝟏). That is, 𝑻(𝟎) is 𝓞(𝟏).

Now, consider what happens when 𝒏 > 𝟎. The condition of line (𝟏) is false, and so we execute
only lines (𝟏) and (𝟑). Line (𝟏) takes 𝒃 time i.e., 𝓞(𝟏) time, and line (𝟑) takes 𝒂 time for the
multiplication and assignment, plus 𝑻(𝒏 − 𝟏) for the recursive call to 𝑭𝒂𝒄𝒕. That is, for 𝒏 > 𝟎,
the running time of 𝑭𝒂𝒄𝒕 is 𝒃 + 𝑻(𝒏 − 𝟏). We can thus define 𝑻(𝒏) by the following recurrence
relation:

𝒂 𝒊𝒇 𝒏 = 𝟎 𝓞(𝟏) 𝒊𝒇 𝒏 = 𝟎
𝑻(𝒏) = { 𝑶𝑹 𝑻(𝒏) = {
𝑻(𝒏 − 𝟏) + 𝒃 𝒊𝒇 𝒏 > 𝟎 𝑻(𝒏 − 𝟏) + 𝓞(𝟏) 𝒊𝒇 𝒏 > 𝟎

Here, 𝑻(𝒏) represents the runtime of 𝑭𝒂𝒄𝒕(𝒏), 𝑻(𝒏 − 𝟏) represents the runtime of the recursive
call to 𝑭𝒂𝒄𝒕(𝒏 − 𝟏), and the additional 𝓞(𝟏) term represents the constant work we do outside
the recursive call. Since the recurrence relation will be used to calculate time complexities, having
an exact number for this constant term does not matter.

I.7.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, namely the iterative substitution method,
the recurrence tree method, and the master theorem to analyze recurrence relations. Solutions to
recurrence relations give the time complexity of the underlying algorithms.

Dr. Dabba Ali 18/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

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 1) Write out the recursive terms (𝑻(𝒏 − 𝟏), 𝑻(𝒏 − 𝟐), … , 𝒆𝒕𝒄. ), as their own recurrence
relations and substitute 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.

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
𝑻(𝒏) = 𝓞(𝟏)).

Example 1:
𝓞(𝟏) 𝒊𝒇 𝒏 = 𝟎
Consider the Recurrence : 𝑻(𝒏) = {
𝑻(𝒏 − 𝟏) + 𝓞(𝟏) 𝒊𝒇 𝒏 > 𝟎
Solve the following recurrence relation using the iterative substitution method ?

Solution:

From now on, we will substitute 𝓞(𝟏) with the constant 𝟏. This simplifies our math without
changing the result of our analysis.
𝟏 𝒊𝒇 𝒏 = 𝟎
𝑻(𝒏) = {
𝑻(𝒏 − 𝟏) + 𝟏 𝒊𝒇 𝒏 > 𝟎
Now, let’s follow the procedure specified above.

𝑻(𝒏) = 𝑻(𝒏 − 𝟏) + 𝟏

= (𝑻(𝒏 − 𝟐) + 𝟏) + 𝟏 = 𝑻(𝒏 − 𝟐) + 𝟐

= (𝑻(𝒏 − 𝟑) + 𝟏) + 𝟐 = 𝑻(𝒏 − 𝟑) + 𝟑

⋮ ⋮ ⋮

= 𝑻(𝒏 − 𝒌) + 𝒌

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 (𝒏 − 𝒌) = 𝟎 ⟹ 𝒌 = 𝒏

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

𝑻(𝒏) = 𝑻(𝟎) + 𝒏
Now we substitute the value of 𝑻(𝟎) to get the solution.

𝑻(𝒏) = 𝒏 + 𝟏 = 𝓞(𝒏)

Dr. Dabba Ali 19/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

Example 2:

𝟐 𝒊𝒇 𝒏 = 𝟏
Consider the Recurrence : 𝑻(𝒏) = { 𝒏
𝟐𝑻 (𝟐) + 𝒏 𝒊𝒇 𝒏 > 𝟏

Solve the following recurrence relation using the iterative substitution method ?

Solution:
𝒏
𝑻(𝒏) = 𝟐𝑻 ( ) + 𝒏
𝟐
𝒏 𝒏 𝒏
= 𝟐[𝑻 ( ) + ] + 𝒏 = 𝟒𝑻 ( ) + 𝟐𝒏
𝟒 𝟐 𝟒
𝒏 𝒏 𝒏
= 𝟒[𝟐𝑻 ( ) + ] + 𝟐𝒏 = 𝟖𝑻 ( ) + 𝟑𝒏
𝟖 𝟒 𝟖
𝒏 𝒏 𝒏
= 𝟖[𝟐𝑻 ( ) + ] + 𝟑𝒏 = 𝟏𝟔𝑻 ( ) + 𝟒𝒏
𝟏𝟔 𝟖 𝟏𝟔
⋮ ⋮ ⋮
𝒏
= 𝟐𝒌 𝑻 ( ) + 𝒌. 𝒏 ; 𝟏 ≤ 𝒌 ≤ 𝒍𝒐𝒈𝟐 𝒏
𝟐𝒌
The maximum value of 𝒌 = 𝒍𝒐𝒈𝟐 𝒏 (then only we get 𝑻(𝒏))
𝒏
𝑻(𝒏) = 𝟐𝒍𝒐𝒈𝟐 𝒏 𝑻 ( ) + 𝒏. 𝒍𝒐𝒈𝟐 𝒏
𝟐𝒍𝒐𝒈𝟐 𝒏
= 𝒏. 𝑻(𝟏) + 𝒏. 𝒍𝒐𝒈𝟐 𝒏

= 𝟐𝒏 + 𝒏. 𝒍𝒐𝒈𝟐 𝒏

= 𝓞(𝒏 𝒍𝒐𝒈 𝒏)

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.

Dr. Dabba Ali 20/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis
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.
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.

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:

𝒏 𝒏 𝒏 𝒏
𝑻( ) 𝑻( ) 𝑻( ) 𝑻( )
𝟐 𝟐 𝟐 𝟐

𝒏
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.

𝒏 𝒏 𝒏 𝒏
𝟐 𝟐 𝟐 𝟐

𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏
𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( ) 𝑻( )
𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒

By repeating this process to the base case, we can construct the full recursion tree.

Dr. Dabba Ali 21/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

𝒏
Level Recursion Tree for 𝑻(𝒏) = 𝟒𝑻 (𝟐) + 𝒏 Work

𝑻(𝒏) 𝒏 𝒏

𝒏 𝒏 𝒏 𝒏 𝒏 𝒏
𝑻( ) 𝟒(𝟐) = 𝟐n

𝒍𝒐𝒈𝟐 𝒏
𝟐 𝟐 𝟐 𝟐 𝟐

𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏 𝒏
𝑻( ) 𝟏𝟔( ) = 𝟒𝒏
𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒 𝟒

𝒏 ⋮ ⋮ 𝒏
𝑻 ( 𝒊) ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝟒𝒊 ( 𝒊 ) = 𝟐𝒊 𝒏
𝟐 𝟐
𝑻(𝟏) 𝑻(𝟏) 𝑻(𝟏) ⋯⋯⋯ ⋯⋯⋯⋯⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ 𝑻(𝟏)
𝒏𝟐 𝑻(𝟏)

𝟒𝒍𝒐𝒈𝟐 𝒏 = 𝒏𝒍𝒐𝒈𝟐 𝟒 = 𝒏𝟐
𝑻𝒐𝒕𝒂𝒍 = 𝒏 + 𝟐𝒏 + 𝟒𝒏 + ⋯ + 𝟐𝒍𝒐𝒈𝟐 𝒏−𝟏 𝒏 + 𝒏𝟐 𝑻(𝟏)
= 𝒏[𝟏 + 𝟐 + 𝟒 + ⋯ + 𝟐𝒍𝒐𝒈𝟐 𝒏−𝟏 ] + 𝒏𝟐 𝑻(𝟏)
𝒍𝒐𝒈𝟐 𝒏−𝟏

= 𝒏 ∑ 𝟐𝒊 + 𝒏𝟐 𝑻(𝟏)
𝒊=𝟎

𝟐𝒍𝒐𝒈𝟐 𝒏−𝟏 − 𝟏 𝒏−𝟐

= 𝒏( ) + 𝒏𝟐 𝑻(𝟏) = 𝒏 ( ) + 𝒏𝟐 𝑻(𝟏)
𝟐−𝟏 𝟏

= 𝓞(𝒏𝟐 )
Summary:
𝒏
Let 𝑻(𝒏) is defined by the recurrence relation : 𝑻(𝒏) = 𝒂𝑻 (𝒃) + 𝒇(𝒏)

where 𝒂 ≥ 𝟏 and 𝒃 > 𝟏 are constants and 𝒇(𝒏) is an asymptotically positive function.
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 : 𝒏𝒍𝒐𝒈𝒃𝒂 . 𝑻(𝟏) + ∑𝒊=𝟎𝒃 𝒂𝒊 𝒇(𝒃𝒊 )

Dr. Dabba Ali 22/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

3) Master Theorem

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 𝒏.)

• 𝒏 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.
The Master Theorem provides a model that can be used to calculate the time complexity of a
preceding recurrence relation. The theorem is defined below:

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 𝑻(𝒏) = 𝓞(𝒏𝒄 ).
More formally,

𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) ) 𝒊𝒇 𝒂 > 𝒃𝒄
𝑻(𝒏) = {𝓞(𝒏𝒄 𝒍𝒐𝒈𝒃 (𝒏)) 𝒊𝒇 𝒂 = 𝒃𝒄
𝓞(𝒏𝒄 ) 𝒊𝒇 𝒂 < 𝒃𝒄

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.

Dr. Dabba Ali 23/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

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.
• 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) Compare the values of a 𝒂 and 𝒃𝒄 to determine which case of the Master Theorem should
be used.
𝒏
Example 1: Consider the following recurrence relation : 𝑻(𝒏) = 𝟒𝑻 (𝟐) + 𝒏

Solve the recurrence by using the master theorem?

Solution:

For this recurrence, we have 𝒂 = 𝟒, 𝒃 = 𝟐, and 𝒇(𝒏) = 𝒏 = 𝓞(𝒏𝟏 ) ⟹ 𝒄 = 𝟏

Since 𝒂 > 𝒃𝒄 , [𝟒 > 𝟐𝟏 ]

As per 𝒄𝒂𝒔𝒆 𝟏 of the master theorem, the solution is : 𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝟐 (𝟒) ) = 𝓞(𝒏𝟐 )
𝒏
Example 2: Consider the following recurrence relation : 𝑻(𝒏) = 𝟐𝑻 (𝟐) + 𝒏

Solve the recurrence by using the master theorem?

Solution:

For this recurrence, we have 𝒂 = 𝟐, 𝒃 = 𝟐, and 𝒇(𝒏) = 𝒏 = 𝓞(𝒏𝟏 ) ⟹ 𝒄 = 𝟏

Since 𝒂 = 𝒃𝒄 , [𝟐 = 𝟐𝟏 ]

As per 𝒄𝒂𝒔𝒆 𝟐 of the master theorem, the solution is : 𝑻(𝒏) = 𝓞(𝒏𝟏 𝒍𝒐𝒈𝟐 (𝒏)) = 𝓞(𝒏 𝐥𝐨𝐠 𝒏)
𝒏
Example 3: Consider the following recurrence relation : 𝑻(𝒏) = 𝟑𝑻 (𝟒) + 𝒏𝟐

Solve the recurrence by using the master theorem?

Solution:

For this recurrence, we have 𝒂 = 𝟑, 𝒃 = 𝟒, and 𝒇(𝒏) = 𝒏𝟐 = 𝓞(𝒏𝟐 ) ⟹ 𝒄 = 𝟐

Since 𝒂 < 𝒃𝒄 , [𝟑 < 𝟒𝟐 ]

As per 𝒄𝒂𝒔𝒆 𝟑 of the master theorem, the solution is : 𝑻(𝒏) = 𝓞(𝒏𝟐 )

𝒏
Example 4: Consider the following recurrence relation : 𝑻(𝒏) = 𝟐𝑻 (𝟐) + 𝒏 𝒍𝒐𝒈 𝒏

Solve the recurrence by using the master theorem?

Dr. Dabba Ali 24/25

Module: Data Structures and Algorithms 3 CHAPTER 1 : Algorithm Analysis

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:
• Case 1: If 𝒂 > 𝒃𝒄 , then 𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) ).
• Case 2: If 𝒂 = 𝒃𝒄 , then
➢ If 𝒌 > −𝟏, then 𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) 𝒍𝒐𝒈𝒌+𝟏 (𝒏)).
➢ If 𝒌 = −𝟏, then 𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) 𝒍𝒐𝒈(𝒍𝒐𝒈(𝒏))).
➢ If 𝒌 < −𝟏, then 𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) ).
• Case 3: If 𝒂 < 𝒃𝒄 , then
➢ If 𝒌 ≥ 0, then 𝑻(𝒏) = 𝓞(𝒏𝑐 𝒍𝒐𝒈𝒌 (𝒏)).
➢ If 𝒌 < 0, then 𝑻(𝒏) = 𝓞(𝒏𝑐 ).
𝒏
Example 1: Consider the following recurrence relation : 𝑻(𝒏) = 𝟑𝑻 (𝟐) + 𝒍𝒐𝒈𝟐 𝒏

Solve the recurrence by using the master theorem or the extended master theorem?

Solution:
Here, the master theorem does not apply, but rather we apply the extended master theorem.
For this recurrence, we have 𝒂 = 𝟑, 𝒃 = 𝟐, and 𝒇(𝒏) = 𝓞( 𝒍𝒐𝒈 𝒏) ⟹ 𝒄 = 𝟎 & 𝒌 = 𝟏

Since 𝒂 > 𝒃𝑐 , [𝟑 > 𝟐𝟎 ]

As per 𝒄𝒂𝒔𝒆 𝟏 of the extended master theorem, the solution is :

𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) ) = 𝓞(𝒏𝒍𝒐𝒈𝟐 (𝟑) )

𝒏
Example 2: Consider the following recurrence relation : 𝑻(𝒏) = 𝟐𝑻 ( ) + 𝒏 𝒍𝒐𝒈 𝒏
𝟐

Solve the recurrence by using the master theorem or the extended master theorem?
Solution:
Here, the master theorem does not apply, but rather we apply the extended master theorem.
For this recurrence, we have 𝒂 = 𝟐, 𝒃 = 𝟐, and 𝒇(𝒏) = 𝓞(𝒏 𝒍𝒐𝒈 𝒏) ⟹ 𝒄 = 𝟏 & 𝒌 = 𝟏

Since 𝒂 = 𝒃𝑐 , [𝟐 = 𝟐𝟏 ]
As per 𝒄𝒂𝒔𝒆 𝟐 of the extended master theorem, 𝒌 = 𝟏 ⟹ 𝒌 > −𝟏, the solution is :

𝑻(𝒏) = 𝓞(𝒏𝒍𝒐𝒈𝒃(𝒂) 𝒍𝒐𝒈𝒌+𝟏 (𝒏)) = 𝓞(𝒏𝒍𝒐𝒈𝟐 𝟐 𝒍𝒐𝒈𝟐 𝒏) = (𝒏 𝒍𝒐𝒈𝟐 𝒏)

Dr. Dabba Ali 25/25