Fundamentals of the Analysis of Algorithm

Efficiency

Jiří Dvorský, Ph.D.

Presentation status to date March 23, 2026
Department of Computer Science
VSB – Technical University of Ostrava

148/382
Lecture Outline

Fundamentals of the Analysis of Algorithm Efficiency

Basics of Algorithm Complexity Analysis
Worst, Best and Average Case
Asymptotic Notation of Complexity
Analysis of Non-Recursive Algorithms
Analysis of Recursive Algorithms

149/382
Fundamentals of the Analysis of Algorithm
Efficiency
Basics of Algorithm Complexity Analysis
Algorithm analysis

What to analyze?

• correctness
• time complexity
• space complexity
• optimality

Possible approaches

• empirical and
• theoretical

150/382
Time and Space Complexity of an Algorithm

• Time complexity – how long the algorithm will run.

• Space complexity – how much extra memory the
algorithm will need in addition to the storage required for
the data itself.
• Previously, both resources were critical.
• Thanks to advances in computing technology, memory is
relatively abundant.
• We will examine time complexity – significant progress can
be made here.
• It turns out that space complexity can be studied using
the same apparatus as time complexity.

151/382
Measuring Input Size

• Trivial observation – larger data usually takes an

algorithm longer to process.
• We introduce the parameter 𝑛 denoting the size of the
input data, which represents for example:
• searching in a list, array – length of the array
• evaluating the polynomial 𝑝(𝑥) = 𝑎𝑛 𝑥 𝑛 + ⋯ + 𝑎1 𝑥 + 𝑎0 at
point 𝑥 – degree of the polynomial
• multiplying matrices of type 𝑛 × 𝑛 – dimension of the
matrix. The actual number of input numbers is 𝑛2 , but this
still depends on 𝑛
• spell checking – number of characters or number of words,
depending on what the algorithm works with

152/382
Measuring Input Size (cont.)

• primality testing – the input is always a single number, the

running time depends on the size of the number (compare
testing 23 and 264 ), the input size will be the number of
bits required to write the number

𝑛 = ⌊log2 𝑎⌋ + 1 (1)

• graph problems – number of vertices and/or number of

edges – here we already have two parameters

153/382
Empirical Measurement of Complexity

• We provide suitable input data and measure the

program’s running time in standard units of time.
• Disadvantages:
• Dependence on specific hardware, implementation
method, and compiler.
• We want to measure algorithm complexity – we do not
have the means to capture the aforementioned influences.
• Hardware development – does this mean algorithms are
accelerating? No, they remain the same.
• The number of operations performed by the program can
be difficult to determine.
• We want to avoid implementation – after all, we are
examining algorithms.

154/382
Time complexity of the algorithm

Time complexity of the algorithm will be expressed

(measured) by the number of performed basic operations with
respect to (as a function of) the size of the input 𝑛:

𝑇(𝑛) ≈ 𝑐𝑜𝑝 𝐶(𝑛),

where

• 𝑛 is the size of the input,

• 𝑇(𝑛) is the running time of the algorithm,
• 𝑐𝑜𝑝 is the time to perform one basic operation and
• 𝐶(𝑛) is the number of basic operations.

155/382
Basic Operations

Typical operations for a given algorithm that significantly

contribute to the overall “running time” of the algorithm.

Problem Input size Basic operation

Searching for an Number of ele- Comparing ele-
element in a list ments in the list ments
Matrix multiplica- Matrix dimensions Arithmetic opera-
tion tions (multiplica-
tion)
Primality testing Number of bits of Dividing numbers
the number
Graph problems Number of vertices Processing a ver-
and/or edges tex or traversing an
edge
156/382
Order of Growth of Complexity

Regarding the relationship

𝑇(𝑛) ≈ 𝑐𝑜𝑝 𝐶(𝑛),

we must approach it with caution, because

1. 𝐶(𝑛) does not take into account the influence of

operations other than basic ones and
2. 𝑐𝑜𝑝 cannot be reliably determined.

We understand this relationship as a reasonable estimate of

the algorithm’s running time, except for extremely small 𝑛.

157/382
Order of Growth of Complexity (cont.)

Problem
How many times faster will my algorithm run on a computer
that is 10× faster than my current computer?

Solution
Of course, 10×, 𝑐𝑜𝑝 is one-tenth.

158/382
Order of Growth of Complexity (cont.)
Problem
How many times longer will my algorithm run for a
twice-as-large input when 𝐶(𝑛) = 12 𝑛(𝑛 − 1)?

Solution
We approximate from above the number of operations 𝐶(𝑛)
1 1 1
𝐶(𝑛) = 𝑛(𝑛 − 1) = 𝑛2 − 𝑛
2 2 2
However, in the context of order of growth, lower-order terms
like − 12 𝑛 are typically ignored. Thus,

1 2
𝐶(𝑛) = 𝑛
2
159/382
Order of Growth of Complexity (cont.)

and
1
𝐶(2𝑛) = (2𝑛)2 = 2𝑛2
2
Therefore,
𝐶(2𝑛) 2𝑛2
= 1 =4
𝐶(𝑛) 𝑛2
2

160/382
Order of Growth of Complexity (cont.)

Remarks
• The base of the logarithm is not significant:
log𝑎 𝑛 = log𝑎 𝑏 ⋅ log𝑏 𝑛.
• A computer with a speed of 1012 (one trillion) operations
per second would take approximately 40 billion years to
perform 2100 ≈ 1.3 ⋅ 1030 operations. The age of the Earth
is approximately 4.4 billion years.
• We will not even consider performing 100! operations...

Algorithms with exponential or factorial order of complexity

are only usable for very small input sizes!

161/382
Order of Growth of Complexity (cont.)

Problem
How many times longer will my algorithm run for a
twice-as-large input, for algorithms with different orders of
growth?

𝑛 log2 𝑛 𝑛 𝑛 log2 𝑛 𝑛2 𝑛3 2𝑛 𝑛!
2𝑛 +1 2× ≈ 2× 4× 8× (… )2 n/a

because
log2 (2𝑛) = log2 2 + log2 𝑛 = 1 + log2 𝑛

22𝑛 = (2𝑛 )2

162/382
Fundamentals of the Analysis of Algorithm
Efficiency
Worst, Best and Average Case
Worst, Best and Average Case

• The number of basic operations is expressed as a function

with one parameter 𝑛, the input size.
• Some algorithms may have different numbers of basic
operations even for the same 𝑛, such as the linear search
algorithm.
Input : Array 𝐴[0 … 𝑛 − 1] and the target element 𝑥
Output: Index of the first occurrence of element 𝑥 in
array 𝐴, otherwise -1
1 for 𝑖 ← 0 to 𝑛 − 1 do
2 if 𝐴[𝑖] = 𝑥 then
3 return i;
4 end
5 end
6 return -1; 163/382
Worst, Best and Average Case (cont.)

Significant numbers of basic operations:

• 𝐶𝑤𝑜𝑟𝑠𝑡 (𝑛) – worst case, highest number of operations

• 𝐶𝑏𝑒𝑠𝑡 (𝑛) – best case, lowest number of operations
• 𝐶𝑎𝑣𝑔 (𝑛) – average case, average number of operations.

164/382
Worst-case scenario 𝐶𝑤𝑜𝑟𝑠𝑡 (𝑛)

• We analyze the algorithm and look for an input of size 𝑛

that results in the maximum possible number of
operations.
• The worst-case scenario provides an upper bound on
complexity, all other cases are either the same or better.
• A low number of operations in the worst case – good news.

Example
Linear search: element 𝑥 in array 𝐴 is not found or is found at
the end, thus 𝐶𝑤𝑜𝑟𝑠𝑡 (𝑛) = 𝑛.

165/382
Best-case scenario 𝐶𝑏𝑒𝑠𝑡 (𝑛)

• Generally, we seek an input of size 𝑛 for which the

algorithm performs the smallest number of operations.
• The average best-case scenario is not as crucial as the
worst-case scenario.
• Inputs are ”similar” and ”close” to the best case. Sorting
nearly sorted sequences.
• A best-case scenario with a ”frightening” number of
operations – generally bad news and ”final” for the
algorithm. But for an encryption algorithm, a ”frightening”
number of cryptanalysis operations is necessary even in
the best case.
Example
Linear search: element 𝑥 is the first element in array 𝐴,
𝐶𝑏𝑒𝑠𝑡 (𝑛) = 1. 166/382
Average case 𝐶𝑎𝑣𝑔 (𝑛)

• Number of operations in the average, “typical”, “random”

case (best and worst cases are extremes).
• It is not the average of the best and worst case!
• We must take into account the probabilities of individual
possible inputs of size 𝑛.
• Analysis of the average case is thus more complicated
than the previous two.
• There are algorithms where the worst and average number
of operations differ significantly, for example QuickSort.

167/382
Average Case 𝐶𝑎𝑣𝑔 (𝑛) – Linear Search

Assumptions

1. probability of successful search 𝑝, where 0 ≤ 𝑝 ≤ 1

2. probability of finding at all positions in the array is the
𝑝
same and equals 𝑛

168/382
Average Case 𝐶𝑎𝑣𝑔 (𝑛) – Linear Search (cont.)

Successful Search

• finding at the first position – one comparison with

𝑝
probability 𝑛 ,
• finding at the second position – two comparisons with
𝑝
probability 𝑛 , and so on, thus

𝑝 𝑝 𝑝 𝑝
1 +2 +⋯+𝑖 +⋯+𝑛
𝑛 𝑛 𝑛 𝑛

169/382
Average Case 𝐶𝑎𝑣𝑔 (𝑛) – Linear Search (cont.)

Unsuccessful Search

• probability of failure is 1 − 𝑝 and we perform 𝑛

comparisons, i.e., 𝑛(1 − 𝑝)

From this
𝑝 𝑝 𝑝 𝑝
𝐶𝑎𝑣𝑔 (𝑛) = (1 + 2 + ⋯ + 𝑖 + ⋯ + 𝑛 ) + 𝑛(1 − 𝑝)
𝑛 𝑛 𝑛 𝑛
𝑝
= (1 + 2 + ⋯ + 𝑖 + ⋯ + 𝑛) + 𝑛(1 − 𝑝)
𝑛
𝑝 1
= [ 𝑛(𝑛 + 1)] + 𝑛(1 − 𝑝)
𝑛 2
1
= 𝑝(𝑛 + 1) + 𝑛(1 − 𝑝)
2

170/382
Average Case 𝐶𝑎𝑣𝑔 (𝑛) – Linear Search (cont.)

Analysis

• always successful search, 𝑝 = 1 and thus 𝐶𝑎𝑣𝑔 (𝑛) = 12 (𝑛 + 1)

• unsuccessful search, 𝑝 = 0 and thus 𝐶𝑎𝑣𝑔 (𝑛) = 𝑛

171/382
Amortized Complexity

• We do not examine a single, isolated run of the algorithm,

but rather examine a “set” of runs with different inputs of
the same size.
• We are interested in the total number of operations for
the set.
• The number of operations for one input from the set may
be high, but it is balanced, “amortized” by a significantly
smaller number of operations for other inputs from the
set.
• For example, one of the inputs causes a significant change
in the data structure, making the processing of
subsequent inputs easier.
• In industry, for example, the purchase of an expensive
machine is amortized by cheaper production of products.
172/382
Sources for Independent Study

• Book [1], chapter 2.1, pages 42 – 51

• Book [2], chapter 2.2, pages 25 – 34 partially

173/382
Fundamentals of the Analysis of Algorithm
Efficiency
Asymptotic Notation of Complexity
Big O Notation

Definition
Let us have functions 𝑡(𝑛) and 𝑔(𝑛), where 𝑡(𝑛), 𝑔(𝑛) ∶ ℕ → ℕ.
We say that function 𝑡(𝑛) belongs to 𝑂(𝑔(𝑛)), if there exists a
positive non-zero real constant 𝑐 and a natural number
𝑛0 ≥ 0 such that
𝑡(𝑛) ≤ 𝑐𝑔(𝑛)

for all 𝑛 ≥ 𝑛0 .

Remark
Instead of saying ”𝑡(𝑛) belongs to 𝑂(𝑔(𝑛))”, we can say that
”𝑡(𝑛) is of order 𝑂(𝑔(𝑛))”.

174/382
Big O notation graphically

𝑡(𝑛) ∈ 𝑂(𝑔(𝑛))

𝑡(𝑛)
𝑐𝑔(𝑛)

irrelevant

𝑛0 𝑛

175/382
Big O notation – formally correct graph

Formally, the domain 𝑡(𝑛)

of definition and the 𝑐𝑔(𝑛)

range of values of
functions 𝑡(𝑛) and

irrelevant
𝑔(𝑛) are natural
numbers ⇒ the graph
should consist only of
points, not curves. 𝑛
𝑛0

If we interpolate the points with a curve ⇒ we obtain

continuous functions ⇒ we can use mathematical analysis
(limits, derivatives, etc.) for calculations.

176/382
Big O notation – example 1

Problem statement
Prove that 3𝑛 + 7 ∈ 𝑂(𝑛).
60
Solution 3𝑛 + 7
4𝑛
1. We seek constants 𝑐
40
and 𝑛0 such that

3𝑛 + 7 ≤ 𝑐𝑛 20

holds for all 𝑛 ≥ 𝑛0 . 0

0 5 10 15
2. It is clear that
necessarily 𝑐 > 3. If we
choose, for example,
𝑐 = 4, then 𝑛0 = 7.
177/382
Big O notation – example 2

Problem statement
Prove that 3𝑛 + 7 ∈ 𝑂(𝑛2 ).
3𝑛 + 7
𝑛2
Solution 40

1. We are looking for

constants 𝑐 and 𝑛0
20
such that

3𝑛 + 7 ≤ 𝑐𝑛2
0
0 5 10 15
holds for all 𝑛 ≥ 𝑛0 .
2. If we choose 𝑐 = 1,
then 𝑛0 = 5.

178/382
Big O notation – example 3

Problem statement
Prove that 100𝑛 + 5 ∈ 𝑂(𝑛2 ).

Solution
1. It holds that 4000
100𝑛 + 5
100𝑛 + 5 ≤ 100𝑛 + 𝑛 for all 101𝑛2
3000
𝑛 ≥ 5.
2. Furthermore, it holds that 2000
101𝑛 ≤ 101𝑛2 . 1000
3. From this 0
0 2 4 6
2
100𝑛 + 5 ≤ 101𝑛 ≤ 101𝑛

and thus 𝑐 = 101 and

179/382
𝑛0 = 5.
Big O notation – example 3 (cont.)

The proof can also be conducted as follows:

100𝑛 + 5 ≤ 100𝑛 + 5𝑛 = 105𝑛

for all 𝑛 ≥ 1. This implies that

105𝑛 ≤ 105𝑛2

and thus 𝑐 = 105 and 𝑛0 = 0.

The definition of Big O notation does not say anything about
the uniqueness of the values 𝑐 and 𝑛0 , it only requires their
existence.

180/382
Omega notation

Definition
Given functions 𝑡(𝑛) and 𝑔(𝑛), where 𝑡(𝑛), 𝑔(𝑛) ∶ ℕ → ℕ. We
say that function 𝑡(𝑛) belongs to Ω(𝑔(𝑛)), if there exists a
positive non-zero real constant 𝑐 and a natural number
𝑛0 ≥ 0 such that
𝑡(𝑛) ≥ 𝑐𝑔(𝑛)

for all 𝑛 ≥ 𝑛0 .

181/382
Lower bound notation graphically

𝑡(𝑛) ∈ Ω(𝑔(𝑛))

𝑡(𝑛)
𝑐𝑔(𝑛)

irrelevant

𝑛0 𝑛

182/382
Ω-notation – example 1

Problem statement 1000

𝑛3
Prove that 𝑛3 ∈ Ω(𝑛2 ). 800 𝑛2

600
Solution
400
1. Clearly, it holds that
200
𝑛3 ≥ 𝑛2 for all 𝑛 ≥ 0.
0
2. Thus we can choose 𝑐 = 1 0 2 4 6 8 10
and 𝑛0 = 0.

183/382
Omega notation – example 2

Problem statement
Prove that 3𝑛 + 7 ∈ Ω(𝑛).

Solution 40
3𝑛 + 7

1. We are looking for 30 3𝑛

constants 𝑐 and 𝑛0 such

20
that
10
3𝑛 + 7 ≥ 𝑐𝑛
0
0 2 4 6 8 10
holds for all 𝑛 ≥ 𝑛0 .
2. The expression 3𝑛 + 7 ≥ 3𝑛
is valid for all 𝑛 ≥ 0, so
𝑐 = 3 and 𝑛0 = 0.
184/382
Theta notation

Definition
Given functions 𝑡(𝑛) and 𝑔(𝑛), where 𝑡(𝑛), 𝑔(𝑛) ∶ ℕ → ℕ. We
say that the function 𝑡(𝑛) belongs to Θ(𝑔(𝑛)), if there exist
positive nonzero real constants 𝑐1 , 𝑐2 and a natural number
𝑛0 ≥ 0 such that

𝑐1 𝑔(𝑛) ≤ 𝑡(𝑛) ≤ 𝑐2 𝑔(𝑛)

for all 𝑛 ≥ 𝑛0 .

185/382
Theta notation graphically

𝑡(𝑛) ∈ Θ(𝑔(𝑛))

𝑡(𝑛)
𝑐1 𝑔(𝑛)
𝑐2 𝑔(𝑛)
irrelevant

𝑛0 𝑛

186/382
Θ-notation – example

Problem Statement
Prove that 12 𝑛(𝑛 − 1) ∈ Θ(𝑛2 ).

Solution

1. First, we prove the right inequality 𝑡(𝑛) ≤ 𝑐2 𝑔(𝑛) (upper

bound)
1 1 1 1
𝑛(𝑛 − 1) = 𝑛2 − 𝑛 ≤ 𝑛2
2 2 2 2
for all 𝑛 ≥ 0.

187/382
Θ-notation – example (cont.)

2. The left inequality 𝑐1 𝑔(𝑛) ≤ 𝑡(𝑛) (lower bound) can be

proven as follows:

1 1 2 1
𝑡(𝑛) = 𝑛(𝑛 − 1) = 𝑛 − 𝑛
2 2 2
1 2 1 1
≥ 𝑛 − 𝑛 𝑛
2 2 2
1 2 1 2
≥ 𝑛 − 𝑛
2 4
1 2
≥ 𝑛
4

In summary, 14 𝑛2 ≤ 12 𝑛(𝑛 − 1) for all 𝑛 ≥ 2.

3. From the previous inequalities, it follows that 𝑐1 = 14 ,
𝑐2 = 12 , and 𝑛0 = 2.

188/382
Θ-notation – example (cont.)
50
1
2
𝑛(𝑛 − 1)
1 2
2
𝑛
40 1 2
𝑛
4

30

20

10

0
0 2 4 6 8 10

189/382
Properties of asymptotic notation

Basic properties:

1. 𝑓(𝑛) ∈ 𝑂(𝑓(𝑛))
2. 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)) ⟺ 𝑔(𝑛) ∈ Ω(𝑓(𝑛))
3. 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)) ∧ 𝑔(𝑛) ∈ 𝑂(ℎ(𝑛)) ⟹ 𝑓(𝑛) ∈ 𝑂(ℎ(𝑛))
4. Θ(𝑓(𝑛)) = 𝑂(𝑓(𝑛)) ∧ Ω(𝑓(𝑛))

190/382
Properties of Asymptotic Notation – Application

Task
Prove that 3𝑛 + 7 ∈ Θ(𝑛).
40
Solution 3𝑛 + 7
4𝑛
30
1. From previous examples, 3𝑛

we know that 3𝑛 + 7 ∈ 𝑂(𝑛) 20

and simultaneously 10
3𝑛 + 7 ∈ Ω(𝑛).
0
2. Therefore, it holds that 0 2 4 6 8 10
3𝑛 + 7 ∈ Θ(𝑛).
3. Specifically, 𝑐1 = 3, 𝑐2 = 4
and 𝑛0 = 7.

191/382
Properties of Asymptotic Notation – Computing Complexity

• Algorithm 𝐴 consists of parts 𝐴1 and 𝐴2 .

• The parts of the algorithm are executed sequentially, i.e.,
after completing 𝐴1 , 𝐴2 begins execution.
• The complexity of part 𝐴1 is 𝑡1 (𝑛) ∈ 𝑂(𝑔1 (𝑛)), the
complexity of part 𝐴2 is 𝑡2 (𝑛) ∈ 𝑂(𝑔2 (𝑛)).
• The question is – what is the overall complexity of
algorithm 𝐴?

192/382
Properties of asymptotic notation – auxiliary lemma

Lemma
Let us have arbitrary real numbers 𝑎1 , 𝑎2 , 𝑏1 , 𝑏2 . Then the
following holds:

𝑎1 ≤ 𝑏1 ∧ 𝑎2 ≤ 𝑏2 ⟹ 𝑎1 + 𝑎2 ≤ 2 max(𝑏1 , 𝑏2 ).

193/382
Properties of asymptotic notation – auxiliary lemma (cont.)
Proof.
From the assumption, we know that

𝑎1 ≤ 𝑏1
𝑎2 ≤ 𝑏2
𝑎1 + 𝑎2 ≤ 𝑏1 + 𝑏2 .

Furthermore, it holds that

𝑏1 + 𝑏2 ≤ 2 max(𝑏1 , 𝑏2 ).

From this, we obtain

𝑎1 + 𝑎2 ≤ 𝑏1 + 𝑏2 ≤ 2 max(𝑏1 , 𝑏2 ).

194/382
Properties of asymptotic notation – computation of complexity

Theorem
If 𝑡1 (𝑛) ∈ 𝑂(𝑔1 (𝑛)) and simultaneously 𝑡2 (𝑛) ∈ 𝑂(𝑔2 (𝑛)), then

𝑡1 (𝑛) + 𝑡2 (𝑛) ∈ 𝑂(max(𝑔1 (𝑛), 𝑔2 (𝑛))).

Remark
The same statement can be expressed for Ω and Θ notation.

195/382
Properties of asymptotic notation – computation of complexity
(cont.)

Proof.
Since 𝑡1 (𝑛) ∈ 𝑂(𝑔1 (𝑛)), there exists a positive non-zero
constant 𝑐1 and a non-negative constant 𝑛1 such that

𝑡1 (𝑛) ≤ 𝑐1 𝑔1 (𝑛) ∀𝑛 ≥ 𝑛1 .

Similarly,
𝑡2 (𝑛) ≤ 𝑐2 𝑔2 (𝑛) ∀𝑛 ≥ 𝑛2 .

196/382
Properties of asymptotic notation – computation of complexity
(cont.)

Proof.
Let 𝑐3 = max(𝑐1 , 𝑐2 ) and 𝑛0 ≥ max(𝑛1 , 𝑛2 ). Then,

𝑡1 (𝑛) + 𝑡2 (𝑛) ≤ 𝑐1 𝑔1 (𝑛) + 𝑐2 𝑔2 (𝑛)

≤ 𝑐3 𝑔1 (𝑛) + 𝑐3 𝑔2 (𝑛) = 𝑐3 [𝑔1 (𝑛) + 𝑔2 (𝑛)]
≤ 2𝑐3 max(𝑔1 (𝑛), 𝑔2 (𝑛)).

Thus, 𝑡1 (𝑛) + 𝑡2 (𝑛) ∈ 𝑂(max(𝑔1 (𝑛), 𝑔2 (𝑛))), since there exist

constants 𝑐 = 2𝑐3 = 2 max(𝑐1 , 𝑐2 ) and 𝑛0 = max(𝑛1 , 𝑛2 ).

The overall complexity of an algorithm is determined by the

part with the highest complexity.

197/382
Properties of asymptotic notation – complexity calculation, ex-
ample

Problem statement
Test whether two identical values occur in the array.

Solution

1. Sorting the array requires no more than 12 𝑛(𝑛 − 1)

comparisons, i.e., a complexity of class 𝑂(𝑛2 ).
2. Comparing all pairs of adjacent elements will require 𝑛 − 1
comparisons, i.e., a complexity of class 𝑂(𝑛).

The overall complexity of the algorithm is therefore

𝑂(max(𝑛2 , 𝑛)) = 𝑂(𝑛2 ).

198/382
Utilization of limits for computations

The growth rate of functions can be more easily calculated

using limits:

0 𝑡(𝑛) grows slower than 𝑔(𝑛)

𝑡(𝑛)
lim = { 𝑐 𝑡(𝑛) grows at the same rate as 𝑔(𝑛)
𝑛→∞ 𝑔(𝑛)
∞ 𝑡(𝑛) grows faster than 𝑔(𝑛)

It is clear that:
𝑡(𝑛) ∈ 𝑂(𝑔(𝑛)) ⇔ 𝑡(𝑛) grows slower or at the same rate as 𝑔(𝑛)
𝑡(𝑛) ∈ Ω(𝑔(𝑛)) ⇔ 𝑡(𝑛) grows at the same rate or faster than 𝑔(𝑛)
𝑡(𝑛) ∈ Θ(𝑔(𝑛)) ⇔ 𝑡(𝑛) grows at the same rate as 𝑔(𝑛)

199/382
Utilization of limits for computations (cont.)

Some useful formulas

L’Hospital’s rule

𝑡(𝑛) 𝑡′ (𝑛)
lim = lim ′
𝑛→∞ 𝑔(𝑛) 𝑛→∞ 𝑔 (𝑛)

Stirling’s formula
𝑛 𝑛
𝑛! ≈ √2𝜋𝑛 ( )
𝑒

200/382
Using limits for calculations – example I

Compare the growth rate of functions 12 𝑛(𝑛 − 1) and 𝑛2 .

1
2
𝑛(𝑛 − 1) 1 𝑛2 − 𝑛
lim = lim
𝑛→∞ 𝑛2 2 𝑛→∞ 𝑛2
1 1
= lim (1 − )
2 𝑛→∞ 𝑛
1 1
= ( lim 1 − lim )
2 𝑛→∞ 𝑛→∞ 𝑛
1 1
= (1 − 0) = > 0
2 2
The functions 12 𝑛(𝑛 − 1) and 𝑛2 grow at the same rate, so
1
𝑛(𝑛 − 1) ∈ Θ(𝑛2 )
2
.
201/382
Utilization of limits for computations – example II

Compare the growth rate of functions log2 𝑛 and √𝑛.

′
log2 𝑛 (log2 𝑛)
lim = lim ′
𝑛→∞ 𝑛→∞ (√𝑛)
√𝑛
(log2 𝑒) 𝑛1 1
𝑛
= lim 1
= (log2 𝑒) lim 1
𝑛→∞ 𝑛→∞
2√𝑛 2√𝑛

2√𝑛
= log2 𝑒 lim
𝑛→∞ 𝑛
1
= 2 log2 𝑒 lim =0
𝑛→∞
√𝑛

The function log2 𝑛 therefore grows more slowly than √𝑛.

202/382
Using limits for computations – example III

Compare the growth rate of the functions 𝑛! and 2𝑛 .

𝑛
√2𝜋𝑛 ( 𝑛 )
𝑛! 𝑒
lim = lim
𝑛→∞ 2𝑛 𝑛→∞ 2𝑛
𝑛𝑛
= √2𝜋 lim √𝑛
𝑛→∞ 2𝑛 𝑒𝑛
𝑛 𝑛
= √2𝜋 lim √𝑛 ( ) = ∞
𝑛→∞ 2𝑒

Remarks
• The function 𝑛! therefore grows faster than 2𝑛 .
• The definition of Θ-notation does not exclude that
𝑛! ∈ Ω(2𝑛 ), but the limit calculation clearly states that 𝑛!
grows faster than 2𝑛
203/382
Basic Complexity Classes

Although theoretically there are infinitely many complexity

classes, the complexity of most algorithms falls into a few
classes.

Class Name Note

1 constant complexity does not depend on the
size of the input; very few algorithms
log 𝑛 logarithmic typically algorithms reducing the size
of the input by a constant factor; in-
terval halving search
𝑛 linear algorithms processing a list of 𝑛 ele-
ments; e.g. sequential search
𝑛 log 𝑛 linearithmic divide and conquer algorithms; aver-
age complexity of QuickSort, Merge- 204/382
Basic Complexity Classes (cont.)
Class Name Note
𝑛2 quadratic generally algorithms with two
nested loops; elementary sorting
methods, summing 𝑛 × 𝑛 matrices
𝑛3 cubic generally algorithms with three
nested loops; multiplying 𝑛 × 𝑛 ma-
trices
2𝑛 exponential
typically generating all subsets of
an 𝑛-element set
𝑛! factorial
typically generating all permuta-
tions of an 𝑛-element set

205/382
Influence of the Multiplicative Constant

• The complexity class is given up to a multiplicative

constant, which is usually not precisely specified.
• Could an algorithm with a higher complexity class
therefore run faster than an algorithm from a better class
for some reasonable 𝑛? For example:
Algorithm Running Time
𝐴 will be better
𝐴 𝑛3
than 𝐵 for 𝑛 < 106 .
𝐵 106 𝑛2
• Multiplicative constants usually take on similar, relatively
small values.
• It can be expected that algorithms with lower complexity
will be better than those with higher complexity already
for moderately large inputs.
206/382
Sources for Independent Study

• Book [1], chapter 2.2, pages 52 – 61

• Book [2], chapters 3.1 and 3.2, pages 49 – 63

207/382
Fundamentals of the Analysis of Algorithm
Efficiency
Analysis of Non-Recursive Algorithms
Finding the Largest Element in an Array of 𝑛 Numbers

Input : Array 𝐴[0 … 𝑛 − 1] of integers

Output: Largest element of array 𝐴
1 𝑚𝑎𝑥 ← 𝐴[0];
2 for 𝑖 ← 1 to 𝑛 − 1 do
3 if 𝐴[𝑖] > 𝑚𝑎𝑥 then
4 𝑚𝑎𝑥 ← 𝐴[𝑖];
5 end
6 end
7 return 𝑚𝑎𝑥;

208/382
Finding the Largest Element in an Array of 𝑛 Numbers (cont.)

Working Procedure

1. Input size – size of array 𝑛

2. Basic operation:
• most frequently performed operations are inside the loop
– comparison 𝐴[𝑖] > 𝑚𝑎𝑥 and assignment 𝑚𝑎𝑥 ← 𝐴[𝑖]
• basic operation will be comparison, because it
• is performed in each iteration of the loop,
• is the key operation for the algorithm, “How many pairs of
elements must I compare to find the maximum?”

3. Number of comparisons is the same for all inputs of size

𝑛, it is not necessary to distinguish between the best,
average, and worst case

209/382
Finding the Largest Element in an Array of 𝑛 Numbers (cont.)

4. Number of basic operations, comparisons, 𝐶(𝑛) will be

equal to
𝑛−1
𝐶(𝑛) = ∑ 1 = 𝑛 − 1 ∈ Θ(𝑛).
𝑖=1

5. Conclusion: Finding the largest element in an array of 𝑛

numbers is a linear algorithm.

210/382
Finding the largest element in an array of 𝑛 numbers, all opera-
tions

Number of operations Description

1 assignment 𝑚𝑎𝑥 ← 𝐴[0]
1 assignment 𝑖 ← 1
𝑛−1 comparison 𝑖 ≤ 𝑛 − 1
𝑛−1 increment 𝑖 by 1
𝑛−1 comparison 𝐴[𝑖] > 𝑚𝑎𝑥
𝑛−1 assignment 𝑚𝑎𝑥 ← 𝐴[𝑖]
1 return result return 𝑚𝑎𝑥
4(𝑛 − 1) + 3 = 4𝑛 − 1 ∈ Θ(𝑛)

Conclusion: Finding the largest element in an array of 𝑛

numbers is a linear algorithm.

211/382
General procedure for determining the time complexity of non-
recursive algorithms

1. Selection of a parameter, or parameters, representing the

size of the input 𝑛.
2. Identification of the basic operations of the algorithm
(these are the ones in the most nested loop!).
3. Does the number of basic operations depend only on the
size of the input? If it depends on something else as well,
we must examine the worst, best, and average cases
separately.
4. Establishment of a relationship, or relationships, (i.e.,
”formulas”) expressing the number, or numbers, of
executions of the basic operations.
5. Simplification of the established relationships and, at
least, determination of the order of growth.
212/382
Useful Summation Formulas

∑(𝑎𝑖 ± 𝑏𝑖 ) = ∑ 𝑎𝑖 ± ∑ 𝑏𝑖 (2)

∑ 𝑐𝑎𝑖 = 𝑐 ∑ 𝑎𝑖 (3)
𝑛 𝑚 𝑛
∑ 𝑎𝑖 = ∑ 𝑎𝑖 + ∑ 𝑎𝑖 (4)
𝑖=1 𝑖=1 𝑖=𝑚+1
𝑢
∑1 = 1 + 1 + ⋯ + 1 = 𝑢 − 𝑙 + 1 (5)
𝑖=𝑙

Specifically
𝑛
∑ 1 = 𝑛 ∈ Θ(𝑛) (6)
𝑖=1

213/382
Useful Summation Formulas (cont.)

𝑛
1 1
∑𝑖 = 1 + 2 + ⋯ + 𝑛 = 𝑛(𝑛 + 1) ≈ 𝑛2 ∈ Θ(𝑛2 ) (7)
𝑖=1
2 2
𝑛
2 2 2 2 1 1
∑𝑖 = 1 + 2 + ⋯ + 𝑛 = 𝑛(𝑛 + 1)(2𝑛 + 1) ≈ 𝑛3 ∈ Θ(𝑛3 ) (8)
𝑖=1
6 3
𝑛
𝑖 2 𝑛 𝑎𝑛+1 − 1
∑𝑎 = 1 + 𝑎 + 𝑎 + ⋯ + 𝑎 = , for 𝑎 ≠ 1 (9)
𝑖=0
𝑎−1
Specifically
𝑛
𝑖 0 1 𝑛 𝑛+1 𝑛
∑ 2 = 2 + 2 + ⋯ + 2 = 2 − 1 ∈ Θ(2 ) (10)
𝑖=0

214/382
Uniqueness of elements in an array

Given is an array of 𝑛 elements. Our task is to analyze the

algorithm that determines whether all elements in the array
are mutually distinct, i.e., unique.
Input : Array 𝐴[0 … 𝑛 − 1]
Output: Returns true if all elements are unique,
otherwise returns false
1 for 𝑖 ← 0 to 𝑛 − 2 do
2 for 𝑗 ← 𝑖 + 1 to 𝑛 − 1 do
3 if 𝐴[𝑖] = 𝐴[𝑗] then
4 return false;
5 end
6 end
7 end
8 return true;
215/382
Uniqueness of elements in an array (cont.)

Visualization of the algorithm Legend

𝑛−1
𝑗
0 pairs that must be
0 tested
an element with itself
does not need to be
𝑖 tested
pairs already tested in
previous iterations of the
𝑛−1 cycle

216/382
Uniqueness of elements in an array (cont.)

Procedure

1. Input size – size of the array 𝑛

2. Basic operation – the most nested cycle contains a single
operation, comparison 𝐴[𝑖] = 𝐴[𝑗]
3. Dependence only on 𝑛? No, the number of basic
operations depends also on whether a duplicate element
appears in the array. Thus, we perform analysis of the
worst, best, and average case.
4. Establishing relationships. For the worst case, it is clear
from the inner cycle that premature termination of the
cycle must not occur, either:
4.1 because all elements are unique or

217/382
Uniqueness of elements in an array (cont.)

4.2 a duplicate appears only in the last pair.

Thus, we perform:
• one comparison for each iteration of the inner cycle, i.e.,
𝑗 = 𝑖 + 1, … , 𝑛 − 1
• the outer cycle iterates 𝑛 − 1 times
Establishing relationships. For the worst case, it is clear
from the inner cycle that premature termination of the
cycle must not occur. Thus, we will perform:
• one comparison for each iteration of the inner cycle, i.e.,
𝑗 = 𝑖 + 1, … , 𝑛 − 1
• the outer cycle iterates 𝑛 − 1 times
Thus, we perform:

218/382
Uniqueness of elements in an array (cont.)

• one comparison for each iteration of the inner cycle, i.e.,

𝑗 = 𝑖 + 1, … , 𝑛 − 1
• outer cycle runs 𝑛 − 1 times

219/382
Uniqueness of elements in an array (cont.)

𝑛−2 𝑛−2
= ∑ [(𝑛 − 1) − (𝑖 + 1) + 1] = ∑(𝑛 − 1 − 𝑖)
𝑖=0 𝑖=0
𝑛−2 𝑛−2
= ∑(𝑛 − 1) − ∑ 𝑖 by (2)
𝑖=0 𝑖=0
𝑛−2
(𝑛 − 2)(𝑛 − 1)
= (𝑛 − 1) ∑ 1 − by (3) and (7)
𝑖=0
2
(𝑛 − 2)(𝑛 − 1)
= (𝑛 − 1)2 − by (5)
2
1 1 2
= 𝑛(𝑛 − 1) ≈ 𝑛 ∈ Θ(𝑛2 )
2 2

220/382
Multiplication of Square Matrices

Our task is to perform an analysis of the algorithm for

computing the product 𝐶 = 𝐴𝐵 of two square matrices 𝐴 and 𝐵
of order 𝑛.
By definition, the elements of the matrix are equal to the scalar
products of the rows of matrix 𝐴 with the columns of matrix 𝐵.

A B C 𝑛−1
𝑐𝑖,𝑗 = ∑ 𝑎𝑖,𝑘 𝑏𝑘,𝑗
* = 𝑘=0
row i C [i, j]
for all
col. j 0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1

221/382
Multiplication of Square Matrices (cont.)

𝐶[𝑖, 𝑗] = 𝐴[𝑖, 0] × 𝐵[0, 𝑗] + ⋯ + 𝐴[𝑖, 𝑘] × 𝐵[𝑘, 𝑗] + ⋯ + 𝐴[𝑖, 𝑛 − 1] × 𝐵[𝑛 − 1, 𝑗]

Input : Two square matrices 𝐴 and 𝐵 of order 𝑛

Output: Square matrix 𝐶 of order 𝑛
1 for each element 𝑐𝑖,𝑗 of matrix 𝐶 do
2 𝑐𝑖,𝑗 = 0;
3 for 𝑘 from 0 to 𝑛 − 1 do
4 𝑐𝑖,𝑗 = 𝑐𝑖,𝑗 + 𝑎𝑖,𝑘 × 𝑏𝑘,𝑗 ;
5 end
6 end

1. The algorithm must compute 𝑛 × 𝑛 elements of matrix 𝐶

222/382
Multiplication of Square Matrices (cont.)

2. Each element of matrix 𝐶 is computed as the scalar

product of the 𝑖-th row of matrix 𝐴 and the 𝑗-th column of
matrix 𝐵
3. The rows and columns have 𝑛 elements that must be
multiplied
4. Therefore, there are a total of 𝑛2 × 𝑛 = 𝑛3 multiplications

223/382
Multiplication of Square Matrices (cont.)

Informal Procedure

1. The algorithm must compute 𝑛 × 𝑛 elements of matrix 𝐶

2. Each element of matrix 𝐶 is computed as the scalar
product of the 𝑖-th row of matrix 𝐴 and the 𝑗-th column of
matrix 𝐵
3. The rows and columns have 𝑛 elements that must be
multiplied
4. Therefore, there are a total of 𝑛2 × 𝑛 = 𝑛3 multiplications

224/382
Multiplication of Square Matrices (cont.)

The running time of the algorithm on a specific computer

𝑇(𝑛) ≈ 𝑐𝑚 𝑀(𝑛) = 𝑐𝑚 𝑛3

if we also count additions

𝑇(𝑛) ≈ 𝑐𝑚 𝑀(𝑛) + 𝑐𝑎 𝐴(𝑛) = 𝑐𝑚 𝑛3 + 𝑐𝑎 𝑛3 = (𝑐𝑚 + 𝑐𝑎 )𝑛3 ,

where 𝑐𝑚 and 𝑐𝑎 are the times required for multiplication and

addition, respectively, and 𝐴(𝑛) is the number of additions,
which satisfies 𝐴(𝑛) = 𝑀(𝑛).

225/382
Multiplication of Square Matrices (cont.)

Summary
The running time of the algorithm may vary depending on the
specific computer, but the order of complexity of the
algorithm (𝑛3 ) remains the same.

226/382
Number of bits in the binary representation of a number

Our task is to analyze the algorithm that for a given natural

number 𝑛 calculates the number of bits necessary for writing
the number 𝑛 in binary.
Input : Natural number 𝑛
Output: Number of bits in the binary representation of
the number 𝑛
1 𝑐𝑜𝑢𝑛𝑡 ← 1;
2 while 𝑛 > 1 do
3 𝑐𝑜𝑢𝑛𝑡 ← 𝑐𝑜𝑢𝑛𝑡 + 1;
4 𝑛 ← ⌊𝑛/2⌋;
5 end
6 return 𝑐𝑜𝑢𝑛𝑡;

227/382
Number of bits in the binary representation of a number (cont.)

• Input size – one number?

• Basic operation – addition, division, comparison with 1?
• Most importantly, in this case, we need to determine the
number of loop iterations. The number of comparisons is
one more than the number of loop iterations.
• The value of the number 𝑛 decreases by half with each
loop iteration, leading to the relation

⌊log2 𝑛⌋ + 1

and which corresponds to the relation (1).

• To derive this, we will need to be able to solve recursive
equations...

228/382
Sources for Independent Study

• Book [1], chapter 2.3, pages 61 – 70

229/382
Fundamentals of the Analysis of Algorithm
Efficiency
Analysis of Recursive Algorithms
Calculation of Factorial

Our task is to analyze the recursive algorithm that calculates

the factorial 𝑛! for a given natural number 𝑛.
1 for 𝑛 = 0
𝑛! = {
𝑛(𝑛 − 1)! otherwise

1 Function F(𝑛)
Input: Natural number 𝑛
Result: Result
2 if 𝑛 = 0 then
3 return 1;
4 end
5 else
6 return 𝑛 ⋅ 𝐹(𝑛 − 1);
7 end
8 end 230/382
Calculation of Factorial (cont.)

• The size of the input is 𝑛.

• We need to find a function 𝑀(𝑛) that represents the
number of multiplications performed by the algorithm.
• The algorithm has a recursive structure, so we can write a
recurrence relation for 𝑀(𝑛).

Remark
To solve the recurrence relation, we need to find an explicit
expression for 𝑀(𝑛). We will use the method of backward
substitution to solve the recurrence relation.

• The recurrence relation is 𝑀(𝑛) = 𝑀(𝑛 − 1) + 1 for 𝑛 > 0.

231/382
Calculation of Factorial (cont.)

• We need to find an initial condition to make the

recurrence relation unique.
• From the algorithm, we can see that when 𝑛 = 0, no
multiplications are performed, so 𝑀(0) = 0.
• Therefore, the complete recurrence relation is

𝑀(𝑛) = 𝑀(𝑛 − 1) + 1 for 𝑛 > 0

𝑀(0) = 0

232/382
Calculation of Factorial (cont.)

• We will solve the recurrence relation using backward

substitution. Substituting 𝑀(𝑛 − 1) = 𝑀(𝑛 − 2) + 1 into
𝑀(𝑛) = 𝑀(𝑛 − 1) + 1, we get

𝑀(𝑛) = [𝑀(𝑛 − 2) + 1] + 1 = 𝑀(𝑛 − 2) + 2

Substituting 𝑀(𝑛 − 2) = 𝑀(𝑛 − 3) + 1 into the previous

equation, we get

𝑀(𝑛) = [𝑀(𝑛 − 3) + 1] + 2 = 𝑀(𝑛 − 3) + 3.

233/382
Calculation of Factorial (cont.)

We can see a pattern emerging: 𝑀(𝑛) = 𝑀(𝑛 − 𝑖) + 𝑖. Using

this formula, we can find an explicit expression for 𝑀(𝑛) by
setting 𝑖 = 𝑛, which gives

𝑀(𝑛) = 𝑀(0) + 𝑛 = 0 + 𝑛 = 𝑛 .

234/382
Calculation of Factorial (cont.)

Summary
1. The result 𝑀(𝑛) = 𝑛 was more or less expected.
2. An iterative algorithm performs the same number of
multiplications as a recursive algorithm, without the
overhead of function calls.
3. However, the approach used to solve the recurrence
relation is important and can be applied to other
problems.

235/382
General procedure for determining the time complexity of recur-
sive algorithms

1. Selection of a parameter, or parameters, representing the

size of the input 𝑛.
2. Identification of the basic operations of the algorithm.
3. Does the number of basic operations depend only on the
size of the input? If it depends on something else as well,
we must examine the worst, best, and average cases
separately.
4. Construction of a recursive relation and suitable initial
conditions, expressing the number of executions of basic
operations.

236/382
General procedure for determining the time complexity of recur-
sive algorithms (cont.)

5. Simplification of the constructed relations and, at least,

determination of the order of growth.

237/382
Tower of Hanoi

• Mathematical puzzle, invented by Édouard Lucas, 1883.

• The puzzle consists of three pegs.
• Initially, several disks of different radii are placed on one
peg, sorted from the largest (at the bottom) to the
smallest (at the top).

• The objective is to move all the disks from the first peg to
the third peg using the second peg.
• Rules of the game:
• Only one disk can be moved at a time.

238/382
Tower of Hanoi (cont.)
• A move consists of taking the upper disk from one of the
pegs and sliding it onto another peg.
• It is forbidden to place a larger disk on top of a smaller
one.
• According to legend, there is a monastery in Hanoi
containing the Towers of Hanoi with 64 golden disks. The
monks move one disk every day at noon. The moment the
last disk is moved, the world will end.
• Don’t panic! Solving this puzzle for 64 disks requires
264 − 1 = 18,446,744,073,709,551,615 moves.
• Even if they moved one disk every second (and proceeded
in the shortest possible way), the time to solve is about
600 billion years.

239/382
Tower of Hanoi (cont.)

Solution steps 1 – 8 Solution steps 9 – 16

240/382
Tower of Hanoi (cont.)

Solving the problem for 𝑛 disks

1. Move 𝑛 − 1 disks from peg A to peg B (using peg C).

2. Move the largest disk from peg A directly to peg C.
3. Move 𝑛 − 1 disks from peg B to peg C (using peg A).

A B C
1 3

For 𝑛 = 1 there is a trivial solution…

241/382
Tower of Hanoi (cont.)

1 Procedure TowerOfHanoi(𝑛, 𝑓𝑟𝑜𝑚, 𝑎𝑢𝑥, 𝑡𝑜)

Input: Number of disks 𝑛, pegs 𝑓𝑟𝑜𝑚, 𝑎𝑢𝑥, 𝑡𝑜
2 if 𝑛 > 0 then
3 TowerOfHanoi (𝑛 − 1, 𝑓𝑟𝑜𝑚, 𝑡𝑜, 𝑎𝑢𝑥);
4 move disk from peg 𝑓𝑟𝑜𝑚 to peg 𝑡𝑜;
5 TowerOfHanoi (𝑛 − 1, 𝑎𝑢𝑥, 𝑓𝑟𝑜𝑚, 𝑡𝑜);
6 end
7 end

Calling

1 TowerOfHanoi(𝑛, 𝐴, 𝐵, 𝐶);

242/382
Tower of Hanoi (cont.)

General procedure

1. Size of the input – number of disks 𝑛.

2. Basic operation – moving a disk.
3. Depends only on 𝑛? Yes. Therefore we do not need to
examine the worst, best, and average cases separately.
4. Establishment of relationships

1 for 𝑛 = 1
𝑀(𝑛) = { (11)
2𝑀(𝑛 − 1) + 1 otherwise

243/382
Tower of Hanoi (cont.)

5. Solving by the backward substitution method. Into the

relation
𝑀(𝑛) = 2𝑀(𝑛 − 1) + 1

we substitute 𝑀(𝑛 − 1) = 2𝑀(𝑛 − 2) + 1

𝑀(𝑛) = 2[2𝑀(𝑛 − 2) + 1] + 1 = 22 𝑀(𝑛 − 2) + 2 + 1,

substituting again 𝑀(𝑛 − 2) = 2𝑀(𝑛 − 3) + 1

𝑀(𝑛) = 22 [2𝑀(𝑛 − 3) + 1] + 2 + 1 = 23 𝑀(𝑛 − 3) + 22 + 2 + 1,

after further substitution we get

𝑀(𝑛) = 24 𝑀(𝑛 − 4) + 23 + 22 + 2 + 1

244/382
Tower of Hanoi (cont.)

After the 𝑖-th substitution we get

𝑀(𝑛) = 2𝑖 𝑀(𝑛 − 𝑖) + 2 𝑖−1 + 2𝑖−2 + ⋯ + 2 + 1

⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
sum according to (10)
𝑖 𝑖
= 2 𝑀(𝑛 − 𝑖) + 2 − 1.

The initial condition valid for 𝑛 = 1 is reached at 𝑖 = 𝑛 − 1

𝑀(𝑛) = 2𝑛−1 𝑀(𝑛 − (𝑛 − 1)) + 2𝑛−1 − 1

= 2𝑛−1 𝑀(1) + 2𝑛−1 − 1
= 2𝑛−1 ⋅ 1 + 2𝑛−1 − 1 = 2 ⋅ 2𝑛−1 − 1 = 2𝑛−1+1 − 1
= 2𝑛 − 1

245/382
Tower of Hanoi (cont.)

6. Conclusion:
6.1 The proposed recursive algorithm performs an exponential
number of basic operations with respect to the input size.
6.2 The algorithm is applicable only for small 𝑛, which is not
caused by an inappropriate design. It is caused by the
nature of the problem – it can be proven that this is the
best possible algorithm.

Be careful with recursive algorithms

In general, recursive algorithms must be approached very
carefully, as their conciseness can mask inefficiency.

246/382
Tower of Hanoi (cont.)

Visualization of recursive calls

𝑛
𝑛−1 𝑛−1
𝑛−2 𝑛−2 𝑛−2 𝑛−2
… … … … … …

2 2 2 2
1 1 1 1 1 1 1 1

The number of nodes corresponds to the number of recursive

function calls
𝑛−1
𝐶(𝑛) = ∑ 2𝑙 = 2𝑛 − 1,
𝑙=0

where 𝑙 is the level number in the tree.

247/382
Resources for Independent Study

• Book [1], chapter 2.4, pages 70 – 79

248/382
Bibliography

1. LEVITIN, Anany. Introduction to the Design and Analysis of

Algorithms. 3rd ed. Boston: Pearson, 2012. isbn
978-0-13-231681-1.
2. CORMEN, Thomas H.; LEISERSON, Charles Eric;
RIVEST, Ronald L.; STEIN, Clifford. Introduction to
algorithms. Fourth edition. Cambridge, Massachusetts: The
MIT Press, 2022. isbn 978-026-2046-305.

249/382
Thanks for your attention

249/382