UDL — FSE/Informatique Algorithm analysis

In the previous chapter, we approached computer science through the lens of problem
solving, noting that solving a problem with the help of computers requires far more than
simply writing instructions that work. True efficiency demands careful attention to how
those instructions are executed. A poorly chosen algorithm or data structure can render
a program impractical, no matter how logically sound it appears, whereas well-chosen
approaches enable solutions to remain effective and scalable as problem sizes grow. At the
heart of this challenge lies the field of algorithm analysis. An algorithm, in its simplest
form, is a finite sequence of well-defined steps that transforms input data into the desired
output, but the central questions that computer scientists must ask go deeper: does the
algorithm always produce the correct result, and if so, how much time and memory will it
require as the input size increases? These questions define the two essential dimensions
of analysis—correctness verification, which ensures that an algorithm terminates with
the intended output for all valid inputs, and complexity analysis, which measures the
computational resources needed as the problem grows. In this sense, algorithm analysis
functions like a microscope, enabling us to look beyond surface-level correctness and
evaluate how well a solution is prepared to meet the demands of real-world data. A simple
example illustrates why such analysis is indispensable: imagine two sorting algorithms,
both capable of producing the correct order for a list of one million numbers. If one
completes the task in seconds while the other requires several hours, only the first is
practically useful. This contrast shows that correctness alone is not enough—efficiency is
equally central. More broadly, algorithm analysis equips us with the means to predict
performance before implementation, to compare competing solutions objectively, to
identify and eliminate bottlenecks, and to understand the very limits of what problems
can be solved efficiently. These skills are not abstract; they are vital in domains such as
big data analytics, machine learning, scientific simulation, and real-time systems, where
inefficiency can turn a feasible task into an impossible one. Ultimately, algorithm analysis
provides a universal language for reasoning about efficiency, independent of programming
languages, hardware platforms, or low-level implementation details.

This chapter is designed to gradually develop your analytical intuition. We begin

by considering correctness, establishing the foundation that algorithms must not only
terminate but also deliver the expected results. From there, we introduce the mathematical
tools of asymptotic notation—Big–O, Ω, Θ, and their variations—which allow us to
describe algorithmic efficiency in precise terms. We then explore best-case, worst-case, and
average-case performance, emphasizing how different perspectives affect our understanding
of computational cost. Building on these foundations, we advance to the analysis
of recursive algorithms, particularly common in divide-and-conquer strategies, using
techniques such as repeated substitution, recursion trees, and the Master Theorem.
Throughout, theoretical explanations will be interwoven with worked examples, visuals,

Khobzaoui Abdelkader 1 2025–2026

UDL — FSE/Informatique Algorithm analysis

and commentary that connect abstract principles to practical applications. By the

conclusion, you will not only be equipped to compute the efficiency of algorithms but also
to interpret these results critically, applying them to select and optimize solutions with
confidence in both theoretical and applied contexts.

By the end of this chapter, you should be able to:

1. Explain what algorithm analysis is and why it plays a central role in computer
science.

2. Distinguish between correctness verification and complexity analysis, with examples

of each.

3. Use asymptotic notations (O, Ω, Θ) to formally describe efficiency.

4. Analyze best-case, worst-case, and average-case performance of algorithms.

5. Apply mathematical tools such as substitution, recursion trees, and the Master
Theorem to solve recurrence relations.

6. Compare and evaluate multiple algorithms objectively based on their time and space
requirements.

7. Relate theoretical analysis to practical implications in large-scale domains like data

science, machine learning, and cloud computing.

8. Cultivate critical thinking about trade-offs in algorithm design, such as simplicity

versus efficiency, or theoretical optimality versus practical usability.

1 Correctness and Efficiency of Algorithms

In the study of algorithm analysis, efficiency often takes center stage, but speed alone
is meaningless if an algorithm does not produce the right results. Before we evaluate
time complexity, memory usage, or scalability, we must first establish a more fundamental
property: correctness. Correctness assures us that, for every valid input, the algorithm
terminates and delivers the intended output. Establishing this property is the foundation
upon which all subsequent evaluation—such as efficiency and scalability—must rest.

Proving correctness is not always trivial, but computer science has developed systematic
methods to approach it. One of the most widely used techniques is mathematical induction,
which is particularly well suited to the recursive and iterative structures of algorithms.
Induction begins with a base case, showing that the algorithm works for the smallest
possible input, then assumes correctness for inputs of size n, and finally demonstrates that

Khobzaoui Abdelkader 2 2025–2026

UDL — FSE/Informatique Algorithm analysis

correctness must also hold for input size n + 1. This reasoning mirrors the incremental
way many algorithms build their solutions. For iterative algorithms, the idea is often
formalized through loop invariants, which are properties that hold true before and after
each loop iteration, ensuring the overall algorithm behaves as expected.

By contrast, disproving correctness requires far less effort: a single counterexample is

sufficient to invalidate an algorithm’s claim. For instance, if a search algorithm claims to
locate an element in any sorted list but fails when duplicate elements are present, that
one failure is enough to prove the design flawed. This asymmetry—where correctness
requires proof for all cases, but incorrectness requires only one counterexample—highlights
the importance of thorough testing and formal reasoning. If an algorithm is shown to
be incorrect, it must be redesigned. This does not always mean starting from scratch;
sometimes the same data structures or techniques can be reused with corrected logic, while
in other cases a deeper reformulation is necessary.

To illustrate these principles, let us examine two fundamental algorithms. The first is
insertion sort, an incremental sorting procedure whose pseudocode is shown in Algorithm 1.

Algorithm 1: Insertion Sort

Input : Array A[1..n] of n elements
Output : Sorted array A[1..n] in nondecreasing order
1 for i ← 2 to n do
2 key ← A[i]
3 j ←i−1
4 while j ≥ 1 and A[j] > key do
5 A[j + 1] ← A[j]
6 j ←j−1
7 A[j + 1] ← key

The key idea behind insertion sort is the maintenance of a loop invariant: at the
beginning of each iteration with index i, the subarray A[1..i − 1] is already sorted. The
base case is immediate since A[1] is trivially sorted. Assuming the invariant holds before
iteration i, the inner loop shifts all larger elements to the right and inserts the current key
into its proper place, thereby preserving sorted order in A[1..i]. By induction, when the
outer loop completes, the entire array A[1..n] is sorted. Termination is straightforward:
the inner loop reduces j at each step, and the outer loop runs only n − 1 times. Thus,
Algorithm 1 is totally correct—it always halts and produces a sorted permutation of the
input.

Khobzaoui Abdelkader 3 2025–2026

UDL — FSE/Informatique Algorithm analysis

A second example is binary search, an efficient method for locating an element within
a sorted array. Its pseudocode is presented in Algorithm 2.

Algorithm 2: Binary Search

Input : Sorted array A[1..n] and target x
Output : Index p such that A[p] = x, or NOT_FOUND
1 low ← 1

2 high ← n

3 while low ≤ high do

4 mid ← ⌊(low + high)/2⌋

5 if A[mid] == x then
6 return mid
7 else if A[mid] < x then
8 low ← mid + 1
9 else
10 high ← mid − 1

11 return NOT_FOUND

Here, the loop invariant states that, at the start of each iteration, if the target element
x is present, then it must lie within the current interval A[low..high]. Initially, this
interval covers the entire array. At each step, the midpoint element is compared with x: if
equal, the search succeeds immediately; if smaller, the interval is narrowed to the right
half; if larger, to the left half. In each case, the invariant is preserved because the new
interval still contains all possible occurrences of x. The loop terminates when low > high,
at which point the interval is empty and the algorithm correctly reports failure. Since
the interval shrinks strictly with each iteration, termination occurs after at most ⌈log2 n⌉
steps. Thus, Algorithm 2 is also totally correct.

These examples demonstrate the general pattern of correctness proofs: begin with
a clearly stated invariant or inductive claim, verify it in the base case, argue that it is
preserved through each step, and conclude correctness for all inputs. Correctness proofs,
reinforced with explicit pseudocode references, not only clarify what an algorithm does but
also explain why it does so reliably. By mastering this approach, one gains the ability to
prove that algorithms terminate, that they produce the intended results, and that they can
be trusted in both theoretical analysis and practical applications. Yet, correctness alone

does not settle the matter of which algorithm is best. When faced with a computational
problem, it is common to discover that more than one algorithmic solution exists. Each
approach may appear valid, yet their performance can differ drastically, making it difficult

Khobzaoui Abdelkader 4 2025–2026

UDL — FSE/Informatique Algorithm analysis

to determine which is the most suitable. This naturally raises a second fundamental
question: by what criteria do we decide which algorithm is preferable? The efficiency of an

algorithm is typically evaluated along two fundamental dimensions: time and space. Time
efficiency refers to how quickly an algorithm completes its task, or in other words, the
number of computational steps required as the input size grows. This measure is called the
time complexity of the algorithm. Space efficiency, on the other hand, concerns the amount
of memory consumed during execution. This measure is called the space complexity of the
algorithm. Together, these two perspectives provide a framework for comparing algorithms
on both speed and memory usage. In practice, time complexity is often emphasized, since
execution time usually dominates performance considerations in large-scale applications.

2 Measuring Algorithmic Efficiency

For any given computational problem, there is rarely a single unique solution. Mul-
tiple algorithms are often available, each reflecting distinct design choices and trade-
offs. Identifying the optimal algorithm—the one that performs best under the relevant
constraints—therefore requires more than proving correctness: it requires judging how
performance scales and why it varies across environments.

The process of algorithm selection is guided by several canonical measures. Time

complexity captures the number of basic operations as a function of input size n. For
instance, a sequential directory scan is O(n), whereas binary search on a sorted directory
is O(log n)—both correct, but dramatically different in scalability. Space complexity
measures the amount of working memory used during execution. Techniques like dynamic
programming decrease time by caching subresults (extra space), while in-place methods
may save memory but cost more time. Storage requirements refer to the use of persistent
storage (secondary memory) for large datasets or intermediate materialization, as in
external sorting or indexing. For data too large to fit in RAM, input/output patterns can
dominate running time.

Ideally we minimize both time and space, but perfection in both dimensions is rarely
achievable. A faster algorithm may require more memory; a memory-frugal one may be
slower. The right choice depends on the deployment context: embedded systems often
privilege space efficiency, while high-throughput cloud services typically prioritize time
efficiency and predictable latency.

Formally, we model performance with two axes: time complexity T (n), which describes
how running time grows with input size n, and space complexity S(n), which tracks how
working memory grows with n. In practice, polynomial-time algorithms (O(1), O(log n),

Khobzaoui Abdelkader 5 2025–2026

UDL — FSE/Informatique Algorithm analysis

O(n), O(n log n), O(n2 )) are generally preferred, while exponential (O(2n )) algorithms are
infeasible beyond small n. Table 1 offers numerical intuition, while Figure 1 visualizes how
these rates diverge.

Table 1: Comparison of Common Time Complexities

Complexity Examples Growth for n = 10, 100, 1000

O(1) Accessing array element 1, 1, 1
O(log n) Binary search 3, 7, 10
O(n) Linear search 10, 100, 1000
O(n log n) Merge sort, heapsort 33, 664, 9966
O(n2 ) Bubble sort, insertion sort 100, 10,000, 1,000,000
O(2n ) Recursive subset generation 1024, ≈ 1030 , infeasible

100

O(log n)
Growth (arbitrary scale)

80
O(n)
O(n2 )
60 O(2 ) (scaled)
n

40

20

0
5 10 15 20 25 30 35 40 45 50
Input Size n

Figure 1: Growth rates of common time complexities

While asymptotic analysis captures how running time scales, the observed execution
time of a concrete program depends on many additional factors. Input size and distribution
play a major role: quicksort, for example, is fast on random inputs but can degrade on
nearly sorted ones with poor pivot selection. The cost model and problem representation
also matter: a “comparison” of big integers is far costlier than that of machine integers, and
the efficiency of graph algorithms depends on whether adjacency lists or matrices are used.
Programming language and compiler quality influence timing as well. Compiled languages

like C/C++ often yield faster code than interpreted ones, and optimizations such as inlining
or vectorization can improve performance. Data structures and memory layout shape cache

Khobzaoui Abdelkader 6 2025–2026

UDL — FSE/Informatique Algorithm analysis

behavior: contiguous arrays benefit from locality, while pointer-based structures incur
cache misses. Hardware characteristics further complicate matters, with CPU speed, cache
sizes, memory bandwidth, and storage type (SSD vs HDD) all affecting results. When data
exceed RAM, I/O becomes the bottleneck, requiring external-memory algorithms designed
to minimize block transfers. Parallelism and concurrency can accelerate computation, but
gains depend on load balancing, synchronization overheads, and the limits of Amdahl’s
law. Even the operating system, runtime environment, and background load can create
variability, as can details of the implementation such as branch prediction friendliness
or use of specialized instructions. Taken together, these observations highlight the dual

nature of performance analysis. Asymptotic complexity provides a high-level, machine-

independent model for comparing algorithms and predicting scalability. Execution time
in practice reflects constant factors, data distributions, and the entire hardware–software
stack. The effective analyst combines both perspectives: using asymptotics to choose
designs, and empirical measurement to validate and tune implementations. By interpreting
the comparisons in Table 1, the growth curves in Figure 1, and the many contextual factors
described above, one develops the judgment required to match algorithms to the demands
of real-world applications.

3 Types of Algorithm Analysis

When studying algorithms, it is not enough to ask what they do; we must also ask how
well they do it. Efficiency determines whether an algorithm can solve large-scale problems
in practice or whether it becomes unusable beyond small inputs. To capture this notion of
performance, two complementary approaches are traditionally employed: apriori analysis,
which is theoretical, and posteriori analysis, which is experimental. Together, they form
the foundation of algorithm evaluation.

Apriori Analysis
Apriori analysis is a theoretical, machine-independent approach conducted before an
algorithm is implemented. The goal is to predict how resource consumption grows as the
input size n increases. The method relies on counting the number of basic operations and
expressing this frequency as a function of n. This abstraction ignores implementation
details such as processor speed, compiler optimizations, or memory hierarchy, focusing
instead on asymptotic notation—Big-O, Θ, and Ω—to classify algorithms by their growth
rate.

Khobzaoui Abdelkader 7 2025–2026

UDL — FSE/Informatique Algorithm analysis

Example (frequency counts).

Program A:
x = x + 2; // frequency: 1 → O(1)

Program B:
for i = 1 to n do
x = x + 2; // frequency: n → O(n)

Program C:
for i = 1 to n do
for j = 1 to n do
x = x + 2; // frequency: n^2 → O(n^2)

Here, the number of operations grows from constant (1), to linear (n), to quadratic
(n2 ). Apriori analysis highlights these differences without ever running the program.
Another example is the linear search algorithm. In the worst case, every element of
a list must be checked, leading to O(n) operations. This conclusion is reached purely
through theoretical reasoning, not experimentation.

Posteriori Analysis
Posteriori analysis is an empirical, machine-dependent approach performed after the
algorithm has been implemented. The algorithm is coded, compiled, and executed on a
real platform, and concrete performance metrics such as execution time, memory usage,
and even energy consumption are measured. Because it involves actual execution, posteriori
analysis is influenced by numerous factors: CPU clock speed, cache and memory hierarchy,
branch prediction, operating system overhead, compiler optimizations, and coding style.
This type of analysis is indispensable for validating theoretical predictions and revealing

constant factors or bottlenecks that asymptotic models ignore. For example, two algorithms
may both run in O(n log n) time, yet one may be consistently faster due to better cache
locality or fewer memory allocations.

Example (empirical test). If we implement linear search in a programming language and

measure its execution time on a real dataset, we are performing posteriori analysis. The
measured results may vary between machines or datasets, even though the asymptotic
bound O(n) remains the same.

Khobzaoui Abdelkader 8 2025–2026

UDL — FSE/Informatique Algorithm analysis

Comparison and Case Study

A clear understanding of apriori and posteriori analysis emerges when we place them side
by side and observe how they complement each other. Apriori analysis provides a universal,
mathematical lens for evaluating scalability before coding, while posteriori analysis delivers
empirical validation through actual execution. Each has strengths and limitations: the
first abstracts away hardware-specific details but ignores constants and bottlenecks, while
the second reveals practical realities but is tied to a specific machine and environment.
This complementarity can be illustrated with the case of Quicksort and Mergesort.

Apriori analysis tells us that both algorithms share the same average-case complexity
of O(n log n), suggesting equal efficiency in theory. Yet posteriori analysis often reveals
important differences: Quicksort typically outperforms Mergesort in practice due to in-place
partitioning, smaller constant factors, and better cache utilization. Conversely, Mergesort
provides guaranteed O(n log n) performance even in the worst case but requires additional
memory. Here, apriori analysis offers the asymptotic guarantee, while posteriori analysis
exposes the real-world trade-offs. The main distinctions between the two approaches are

summarized in Table 2. It highlights how apriori analysis is invaluable for early-stage

algorithm design and theoretical comparison, whereas posteriori analysis is essential for
benchmarking, optimization, and deployment decisions.

Khobzaoui Abdelkader 9 2025–2026

UDL — FSE/Informatique Algorithm analysis

Table 2: Comparison of Apriori and Posteriori Analysis

Aspect Apriori Analysis Posteriori Analysis

Nature Theoretical, machine- Empirical, machine-

independent dependent
Timing Conducted before implemen- Conducted after implementa-
tation tion
Measures Operation counts, asymp- Actual runtime, memory us-
totic complexity (O(n), O(n2 ), age, profiling metrics
etc.)
Independence Independent of hardware, Dependent on CPU, OS, com-
compiler, and language piler, and coding style
Advantages Predicts scalability; reusable Reveals constants and bottle-
across contexts; supports necks; validates theory; guides
early design optimization
Limitations Ignores constants and system- Results are context-specific
level effects and not universally generaliz-
able
Use Cases Algorithm design, academic Benchmarking, regression test-
proofs, theoretical evaluation ing, deployment decisions

In summary, apriori and posteriori analysis are not competing methods but comple-
mentary perspectives. Apriori analysis provides mathematical models for reasoning about
efficiency, while posteriori analysis grounds those models in empirical evidence. Used
together, they ensure that algorithms are not only theoretically elegant but also practically
efficient and reliable in real-world deployment.

4 Algorithm Design Cycle

Designing an efficient algorithm is rarely a linear process; instead, it follows an iterative
cycle in which theory and practice inform and refine one another. The goal of this cycle
is to ensure that an algorithm is both mathematically robust and practically effective.
Figure 2 illustrates this process.

Khobzaoui Abdelkader 10 2025–2026

UDL — FSE/Informatique Algorithm analysis

Problem Statement

Redesign
Algorithm Design Alternative
Algorithms

Theoretical Apriori Analysis

Validation
Theoretical Evaluation

Acceptable No

Complexity?

Yes
New Requirements

Implementation

Optimization
Practical Posteriori Analysis
Tuning Constants
Validation Empirical Testing
Memory Patterns

Meets Performance No

Targets?

Yes

Deployable Solution

Figure 2: Algorithm design cycle. Apriori analysis filters designs before implementation;
posteriori analysis validates on real hardware. If targets are not met, optimization iterates
back to implementation, with an optional redesign loop to the initial design. A positive
decision leads to deployment.

Khobzaoui Abdelkader 11 2025–2026

UDL — FSE/Informatique Algorithm analysis

The cycle begins with a precise problem statement, which is then translated into one
or more candidate algorithmic designs. Before investing in implementation, the first
checkpoint is apriori analysis. At this stage, designers evaluate the asymptotic complexity
of candidate solutions in order to filter out those with poor scalability, such as O(n2 )
or O(2n ). Only designs with promising theoretical growth rates (e.g., O(n log n)) are
considered for further development. Next, the surviving designs move to implementation.

Here the algorithm is expressed concretely in code, using chosen data structures and
programming constructs. Once implemented, the design undergoes posteriori analysis,
where it is tested empirically on representative inputs and hardware. Performance metrics
such as execution time, memory footprint, and cache behavior are collected to verify
whether theoretical predictions align with real-world outcomes. If the posteriori analysis

reveals shortcomings—for example, excessive runtime, high memory usage, or sensitivity

to input characteristics—the design enters an optimization loop. At this stage, engineers
refine the implementation by reducing constant factors, improving memory access patterns,
or exploiting features such as vectorization and parallelism. If micro-optimizations are
insufficient, the process may require a return to the design stage to explore alternative
algorithms. The cycle continues until performance targets are met. Once both theoretical

and empirical requirements are satisfied, the algorithm exits the cycle as a deployable
solution. This structured approach ensures that development resources are focused on
viable designs and that every algorithm is validated at both the abstract and practical
levels.

5 Fundamental Definitions
Before we can study algorithms in detail, we need to establish a common vocabulary.
When computer scientists analyze algorithms, they are not only interested in whether an
algorithm works, but also in how efficiently it uses time and memory as the input size grows.
In this section, we introduce the key concepts and notations that form the foundation of
algorithm analysis. Understanding these terms will allow us to reason about performance
in a precise way, compare different solutions fairly, and predict how an algorithm will
behave on larger inputs.

Definition 0.1 (Algorithmic Complexity). The complexity of an algorithm is the number of

elementary operations it performs on an input of size n. This is expressed as a mathematical
function, such as T (n) for time or S(n) for space.
Example: Linear search in an array of size n requires at most n comparisons, so
T (n) = O(n).

Khobzaoui Abdelkader 12 2025–2026

UDL — FSE/Informatique Algorithm analysis

Definition 0.2 (Elementary Operation). An elementary operation is an operation whose

execution time does not depend on the input size n. Common examples include:

• Arithmetic operations (+, -, *, /, %);

• Comparisons (<, >, =, ̸=, etc.);

• Logical operations (AND, OR, NOT);

• Assignments, array indexing, or the overhead of a simple function call.

Example: Evaluating x + y is an elementary operation because it always takes constant

time.

Definition 0.3 (Data Size). The data size n refers to the number of elements that the
algorithm must process. Its meaning depends on the type of problem:

• Sorting an array: n = number of elements;

• Computing the n-th term of a sequence: n = index of the term;

• Summing an n × m matrix: data size = n · m.

Example: For a 3 × 4 matrix, n · m = 12 elements must be processed.

Definition 0.4 (Time Complexity). The time complexity T (n) of an algorithm measures
the number of elementary operations as a function of input size n.
Example: Binary search on a sorted array of size n has T (n) = O(log n).

Definition 0.5 (Space Complexity). The space complexity S(n) of an algorithm measures
how much memory is required as a function of n, including input storage, temporary
variables, and recursion stack.
Example: Merge Sort requires O(n) extra memory for temporary arrays.

Definition 0.6 (Worst-Case Complexity). The worst-case complexity is the maximum

number of operations an algorithm performs on any input of size n. It represents an upper
bound on the running time.
Example: In linear search, the worst case occurs when the target is absent: T (n) = n
comparisons.

Definition 0.7 (Best-Case Complexity). The best-case complexity is the minimum number
of operations on any input of size n.
Example: In linear search, the best case occurs when the target is the first element:
T (n) = 1.

Khobzaoui Abdelkader 13 2025–2026

UDL — FSE/Informatique Algorithm analysis

Definition 0.8 (Average-Case Complexity). The average-case complexity is the expected

number of operations assuming a probability distribution over inputs.
Example: In linear search, if the target is equally likely to appear in any position, the
expected number of comparisons is (n + 1)/2.

Definition 0.9 (Asymptotic Notations). Asymptotic notations describe how functions grow
as n becomes very large:

• Big-O (O(f (n))): an upper bound (worst case);

• Omega (Ω(f (n))): a lower bound (best case);

• Theta (Θ(f (n))): a tight bound (both upper and lower).

Example: Bubble Sort has worst-case complexity O(n2 ), while Merge Sort runs in
Θ(n log n).

Definition 0.10 (Algorithm Efficiency). An algorithm is considered efficient if it runs in

polynomial time; in other words, if T (n) = O(nk ) for some constant k.
Example: QuickSort (average case O(n log n)) is efficient.

Definition 0.11 (Intractable Problem). A problem is intractable if no polynomial-time

algorithm is known; all known solutions take super-polynomial (often exponential) time.
Example: The Travelling Salesman Problem (TSP) solved by brute force requires
O(n!).

Definition 0.12 (P vs NP). P is the class of decision problems solvable in polynomial

time. NP is the class of decision problems for which a proposed solution can be checked
in polynomial time. The question of whether P = N P is one of the most famous open
problems in computer science.
Example: Checking whether a completed Sudoku puzzle is valid can be done in
polynomial time, so Sudoku belongs to NP.

In this section, we introduced the essential vocabulary of algorithm analysis: complexity

measures, elementary operations, and asymptotic notations. We also distinguished between
best, worst, and average cases to capture different scenarios of execution. These ideas
may seem theoretical at first, but they are extremely practical. When you choose between
two algorithms, it is often the complexity that tells you which one will scale better as
your input grows. Mastering these definitions will help you not only analyze algorithms
rigorously, but also make informed choices in real-world programming and problem solving.
In the next chapters, we will apply these ideas to more advanced techniques such as
analyzing loops, recurrences, and entire algorithmic paradigms.

Khobzaoui Abdelkader 14 2025–2026

UDL — FSE/Informatique Algorithm analysis

6 Why Calculate Complexity?

When studying algorithms, it is not enough to confirm that they eventually produce the
correct answer. Two different algorithms may solve the same problem, but one might take
seconds while the other takes hours—or even years—as the input size grows. This is why
computer scientists calculate complexity: it allows us to measure, in a machine-independent
way, the amount of work an algorithm requires in terms of time and memory. By analyzing
complexity, we can estimate how long an algorithm will take to run, determine whether it
remains practical for large inputs, and compare alternative solutions fairly. In some cases,
we can even prove that a given algorithm is optimal, meaning that no other algorithm
can solve the same problem more efficiently. A simple but illuminating example is the

task of computing the sum of the first N integers. One straightforward method is to add
the numbers sequentially: start with a variable sum equal to zero, and then add 1, then 2,
then 3, and so on until N . This iterative approach is correct and easy to implement, but
its running time grows directly with N , since each new integer requires another addition.
In terms of complexity, this is a linear-time algorithm, denoted O(n). It also requires only
a small, fixed amount of memory (to store the loop counter and the running total), so its
space complexity is constant. However, there exists a far more efficient solution. Instead

of looping, we can use the well-known closed-form formula:

N (N + 1)
Sum(N ) = .
2

This formula computes the sum with just a few arithmetic operations, regardless of how
large N is. Its time complexity is constant, O(1), and its memory usage is also constant.
Both methods are mathematically correct, but the difference in efficiency is dramatic:
while the iterative method becomes slower as N increases, the formula always runs in the
same fixed amount of time. For very large N , this difference can determine whether a
program runs instantly or takes an impractical amount of time. This closed-form solution

is famously attributed to Carl Friedrich Gauss. As a young schoolboy, Gauss was asked to
compute the sum of the numbers from 1 to 100. Rather than performing one hundred
additions, he recognized a pattern: pairing the first and last numbers (1 + 100), the
second and second-to-last (2 + 99), and so forth always produced the same sum, 101.
Since there are fifty such pairs, the total must be 50 × 101 = 5050. From this clever
observation, the general formula emerged. Gauss’s insight perfectly illustrates the essence
of complexity analysis: two correct solutions can differ vastly in efficiency, and recognizing
a more efficient method can save enormous effort. By comparing these two algorithms for

summing integers, we see why complexity matters so much. The iterative algorithm has

Khobzaoui Abdelkader 15 2025–2026

UDL — FSE/Informatique Algorithm analysis

linear time complexity, O(n), while the closed-form solution achieves constant time, O(1).
This means that as N grows, the difference in performance between the two methods
becomes more and more significant. Complexity analysis therefore guides us in choosing
the right algorithm for the job and helps us understand the practical limits of computation.
In real-world applications where input sizes can be enormous, such insights are not just
theoretical—they are essential for writing programs that finish in a reasonable amount of
time.

7 Rules for Calculating Algorithm Complexity

The analysis of algorithms provides a systematic way to determine how many operations
a program executes and how much memory it uses. Instead of depending on machine-
specific execution times, we reason in terms of abstract elementary operations (arithmetic,
comparisons, assignments, etc.). By applying a few simple rules, we can calculate the
exact number of operations required by an algorithm, no matter how complex it is. In
this section, we build these rules step by step, illustrating each with concrete examples.

7.1 Complexity of a Simple Instruction

The most basic unit of analysis is a single instruction. Its cost corresponds to the number
of elementary operations it contains.
Example:
y ←3+5×x

This instruction performs one multiplication (5×x), one addition (3+·), and one assignment
(store result in y). Total cost: 3 operations.

7.2 Complexity of a Sequence of Instructions

When instructions are executed one after another, their costs add up. The total cost of a
sequence is simply the sum of the costs of its individual parts.
Example:

Algorithm Sum
X, y, z: integer;
Begin
read(x)
read(y)
z ← x + y
write(z)
End.

Khobzaoui Abdelkader 16 2025–2026

UDL — FSE/Informatique Algorithm analysis

Here we have: two reads, one addition, one assignment, and one write. Total cost: 5
operations.

7.3 Complexity of Conditional Structures

Conditional statements such as if-then-else introduce two sources of cost:

1. the cost of evaluating the condition,

2. the cost of executing the chosen branch.

If the condition costs Ccond and the branches cost Cthen and Celse , the total cost is:

Ctotal = Ccond + max(Cthen , Celse ).

Example:

if (x > y) then
z ← x - y
else
z ← y - x

Condition: 1 comparison. Each branch: 1 subtraction + 1 assignment = 2. Total cost:

1 + 2 = 3 operations.

7.4 Complexity of Iterative Structures

Loops are one of the most significant contributors to complexity. Each iteration involves
checking the loop condition and executing the body. If a loop executes n times with
condition cost Ccond and body cost Cbody , the rule is:

Ctotal = n · (Ccond + Cbody ) + Cfinal_check .

Example 1 (Linear loop):

for i ← 1 to n do
sum ← sum + i

Body: 1 addition + 1 assignment = 2. Condition + increment: 1. Per iteration: 3. Total:

3n + 1 operations.

Khobzaoui Abdelkader 17 2025–2026

UDL — FSE/Informatique Algorithm analysis

Condition evaluation (Ccond )

Then block (Cthen ) Else block (Celse )

Total cost: Ccond + max(Cthen , Celse )

Figure 3: Cost structure of a simple if-then-else instruction.

Example 2 (Nested loops):

for i ← 1 to n do
for j ← 1 to n do
sum ← sum + 1

Inner loop: (2 for the body +1 for the check) · n + 1 = 3n + 1. Outer loop repeats this n
times: n(3n + 1) + 1 = 3n2 + n + 1 operations.
Example 3 (Halving loop):

while n > 1 do
n ← n / 2

Body: 1 division + 1 assignment = 2. Condition: 1. Each iteration: 3. Number of

iterations: ⌊log2 n⌋. Total: 3⌊log2 n⌋ + 1 operations.

Khobzaoui Abdelkader 18 2025–2026

UDL — FSE/Informatique Algorithm analysis

7.5 Complexity of Functions and Procedures

A function’s cost is the sum of its instructions. A call is not atomic: it expands to include
the cost of its body.
Example:

function square(n: integer): integer

return n * n

Body: 1 multiplication + 1 return = 2. If called inside a loop of n: 2n operations.

k
C(F ) = C(Ij ), where Ij are the instructions of F .
X

j=1

7.6 Complexity of Recursive Algorithms

Recursive algorithms are analyzed with recurrence relations.
If a problem of size n is divided into a subproblems of size n/b, plus extra work f (n),
then:
n
 
T (n) = a · T + f (n).
b
Example (Merge Sort): An array of size n is split into two halves (a = 2, b = 2).
Merging requires n − 1 comparisons and n assignments = 2n − 1 operations. Recurrence:
 
T (n) = 2T n
2
+ (2n − 1).

Khobzaoui Abdelkader 19 2025–2026

UDL — FSE/Informatique Algorithm analysis

Summary Table

Structure Rule with Example (Exact Count)

Simple instruction Count operations. Example: y ← 3 + 5 × x = 3.

Sequence of instructions Add costs. Example: read(x); read(y); z ←
x+y; write(z); = 5.
Conditional Ccond + max(Cthen , Celse ). Example: comparison +
branch = 3.
Loop n(Ccond + Cbody ) + Cfinal . Example: sum 1..n =
3n + 1.
Nested loops Multiply iteration costs. Example: double loop =
3n2 + n + 1.
Halving loop Iterations ⌊log2 n⌋. Example: 3⌊log2 n⌋ + 1.
Function call Expand into body cost. Example: square(n) = 2,
looped n times = 2n.
Recursive algorithm Recurrence T (n) = aT (n/b) + f (n). Example:
Merge Sort = 2T (n/2) + (2n − 1).

Table 3: Rules for calculating algorithm complexity with exact operation counts.

This table summarizes the main rules for calculating exact operation counts. Each
programming structure—whether a simple statement, a conditional, a loop, or a recursive
call—has a clear rule that can be applied directly. The examples illustrate how to translate
code into a cost expression. By practicing these rules, students can analyze any algorithm,
breaking it into parts and combining their costs systematically. Counting exact operations

is a valuable first step in algorithm analysis, because it shows precisely how each instruction
contributes to the total cost. However, these counts quickly become cumbersome and
depend on implementation details. To compare algorithms more generally, we often shift to
a higher-level abstraction: asymptotic complexity. Instead of writing 3n + 1 or 3n2 + n + 1,
we describe how costs grow as input size increases, using notations such as O(n) or O(n2 ).
The next section introduces this asymptotic approach, which provides a universal language
for reasoning about algorithm efficiency.

Khobzaoui Abdelkader 20 2025–2026

UDL — FSE/Informatique Algorithm analysis

8 Asymptotic Complexity
Building precise mathematical models that capture every detail of a program’s execution is
extremely difficult, if not impossible. Different instructions may require different amounts
of time, and the control flow can vary widely depending on the input. Because of this,
determining the exact running time of an algorithm on all possible inputs is generally
infeasible. To overcome this limitation, computer scientists rely on asymptotic complexity
analysis. Rather than attempting to count every single operation, we model the running
time as a function of the input size parameter (commonly n) and study how this function
grows as n becomes large. This abstraction filters away machine- and language-dependent
constants while preserving the essential growth behavior that determines scalability. In
practice, asymptotic analysis enables meaningful comparisons of algorithms, regardless of
the hardware, compiler, or programming language. To make this idea concrete, consider

the classical problem of searching in a list. A linear search inspects elements one by one. If
the list size grows by a factor of 1000, the running time also grows by a factor of 1000—a
direct proportionality known as linear growth. By contrast, a binary search halves the
search space at each step, so increasing the list size by 1000× raises the running time by
only about log2 1000 ≈ 10 steps. This striking difference illustrates why orders of growth
are central in algorithm analysis: what may appear as a small difference in formulas quickly
becomes decisive at scale. The divergence between these growth rates, together with
others such as quadratic and exponential behavior, is illustrated in Figure 4. Because an

400
O(1)
O(log n)
O(n)
300
Growth of f (n)

O(n log n)
O(n2 )
O(2n )
200

100

0
2 4 6 8 10 12 14 16 18 20
Input size n

Figure 4: Comparison of common asymptotic growth rates. For small n, the curves
appear close, but as n grows, exponential and quadratic complexities quickly outpace
linear or logarithmic ones.

algorithm’s running time can vary with the input even for the same n, computer scientists

Khobzaoui Abdelkader 21 2025–2026

UDL — FSE/Informatique Algorithm analysis

define three classical measures. The worst-case complexity corresponds to the maximum
number of steps an algorithm may take on any input of size n, providing a conservative
guarantee that performance will never be worse than this bound. For example, in linear
search, the worst case occurs when the target is absent, requiring n comparisons. The
best-case complexity, by contrast, corresponds to the minimum number of steps, describing
an ideal but rarely representative situation—for linear search, this is when the target is the
first element, requiring only one comparison. Finally, the average-case complexity gives
the expected number of steps over all inputs of size n, assuming a probability distribution;
in linear search, if the target is equally likely to be in any position, the expected number
of comparisons is (n + 1)/2. These three measures are summarized in Table 4, which
highlights the variability in performance across different scenarios.

In practice, worst-case complexity is emphasized because it provides a robust

specification independent of assumptions: it guarantees that every input of size n
will be handled within the stated bound.

Table 4: Comparison of Complexity Measures for Linear Search

Measure Analysis for Linear Search

Best Case O(1) — the target is the first element.
Worst Case O(n) — the target is the last element or absent.
n+1
Average Case O(n) — on average, the target is found after 2 comparisons.
Space Complexity O(1) — only a few variables are needed besides the input.

While these measures highlight variability, analyzing algorithms at the level of exact
instruction counts is both impractical and uninformative. Different machines, compilers,
or coding styles can alter constants, and branching behavior makes precise predictions
infeasible. What truly matters is the order of growth: how running time increases as
input size becomes large. This perspective explains why algorithms with superficially
similar performance on small inputs can diverge drastically at scale. For example, while
a linear-time algorithm (O(n)) and a logarithmic-time algorithm (O(log n)) may appear
competitive for small n, Figure 4 shows that the logarithmic one will vastly outperform
the linear one as n grows. To connect theory to practice, Table 5 summarizes common

growth rates alongside representative algorithms. This complements Figure 4 by linking

abstract curves to real-world examples, helping us appreciate why some algorithms scale
better than others.

Khobzaoui Abdelkader 22 2025–2026

UDL — FSE/Informatique Algorithm analysis

Table 5: Common Growth Rates with Example Algorithms

Complexity Description Example Algorithms

O(1) Constant time — independent of input Accessing an array element, inserting
size in a hash table (average)
O(log n) Logarithmic growth — grows slowly Binary search, balanced BST opera-
with input size tions
O(n) Linear growth — proportional to input Linear search, finding max/min in an
size array
O(n log n) Linearithmic growth — slightly super- Merge Sort, QuickSort (average), Heap-
linear Sort
O(n2 ) Quadratic growth — common with Bubble Sort, Insertion Sort, Selection
nested loops Sort
O(2n ) Exponential growth — impractical for Recursive subset generation, naive Fi-
large n bonacci recursion
O(n!) Factorial growth — extremely ineffi- Traveling Salesman (brute force), per-
cient mutations generation

Because only the long-run trend is important, theoretical analyses describe running
times up to constant multiplicative factors. Thus, functions like 3n + 7 and 5n + 100 are
both considered “linear” since their growth rates are equivalent at scale. To formalize this
reasoning, computer scientists introduce the standard asymptotic notations: Big-O for
upper bounds, Ω for lower bounds, and Θ for tight bounds that serve as both upper and
lower. These notations constitute the common language of algorithm analysis, providing a
rigorous framework for comparing algorithms independently of implementation details and
for reasoning about scalability in a principled way. In the next section, we will formally
define these notations and examine their mathematical properties.

8.1 A Notation for “the Order of” (Big-O)

When studying algorithms, we are seldom interested in the exact number of processor
instructions or the precise execution time on a particular machine. Such details depend
on factors like hardware speed, compiler optimizations, and programming language. What
truly matters is how the required resources grow as the size of the input n increases. To
capture this growth in a way that is both rigorous and independent of implementation
details, computer scientists rely on asymptotic analysis. The most common tool in this
analysis is the Big-O notation, read as “order of.” It provides a mathematical language
for expressing the asymptotic upper bound of a function’s growth rate. Formally, we say

that f (n) = O(g(n)) if there exist constants C > 0 and n0 ∈ N such that |f (n)| ≤ C|g(n)|

Khobzaoui Abdelkader 23 2025–2026

UDL — FSE/Informatique Algorithm analysis

for all n ≥ n0 . Intuitively, this means that beyond some point n0 , the function f (n)
never grows faster than a constant multiple of g(n). The symbol “=” in this expression
must not be misread as equality of functions; instead, it signifies membership: f belongs
to the class of functions asymptotically bounded by g. Thus, O(g(n)) denotes a family
of functions, not a single one. To make this concrete, consider a few examples. The

linear function f (n) = 3n + 2 satisfies f (n) ≤ 4n for all n ≥ 2, hence f (n) = O(n) with
C = 4 and n0 = 2. Similarly, f (n) = 100n is in O(n2 ) because, beyond n = 100, the
quadratic function dominates the linear one. In algorithmic practice, single assignments
or array accesses are constant-time operations, i.e., O(1); a simple loop over n elements
is O(n); and a nested double loop usually yields O(n2 ). From mathematics we also
know that for polynomials only the term of highest degree matters asymptotically: for
instance, f (n) = n2 + 500n + 1000 behaves like n2 for large n, so we write f (n) = O(n2 ).
This principle, sometimes called domination of the largest term, explains why complexity
analysis focuses on leading terms while ignoring constants and lower-order contributions.
Although many functions g can serve as an upper bound, we usually seek the tightest

bound to describe growth as accurately as possible. Saying that a linear function is O(n3 )
is technically correct but as uninformative as saying “this person’s age is less than a
thousand years.” The sharper description O(n) captures the true scale of growth and is
therefore preferred. This notion of tightness is critical when comparing algorithms, since
only the most accurate asymptotic characterization allows fair evaluation of their relative
efficiency. Big-O does not exist in isolation but is complemented by related notations.

Big-Ω provides an asymptotic lower bound, asserting that a function eventually grows
at least as fast as another. Big-Θ offers a tight bound, capturing both the upper and
lower constraints and thus characterizing the exact growth rate up to constant factors.
Finally, little-o notation, f (n) = o(g(n)), describes a strict upper bound, meaning f grows
strictly slower than g, i.e., limn→∞ f (n)/g(n) = 0. These notations together form the core
vocabulary of asymptotic analysis and are frequently used in proofs, complexity tables, and
theoretical discussions. The practical significance of asymptotic notation becomes evident

when comparing algorithms. A linear search through an unsorted list requires at most
O(n) comparisons, while binary search on a sorted list needs only O(log n) comparisons.
For small n, the difference is minor, but as shown in Table 6, logarithmic growth scales
vastly better than linear or quadratic growth. For very large datasets, such as national
identity databases containing millions of records, binary search outperforms linear search
by several orders of magnitude. Figure 5 further reinforces this point by visualizing the
divergence between different growth classes: logarithmic and linear curves rise slowly,
quadratic growth accelerates quickly, and exponential growth becomes infeasible almost
immediately.

Khobzaoui Abdelkader 24 2025–2026

UDL — FSE/Informatique Algorithm analysis

n O(1) O(log n) O(n) O(n log n) O(n2 ) O(2n )

10 1 3 10 30 100 1024
50 1 6 50 282 2500 1.13 × 1015
100 1 7 100 664 10000 1.27 × 1030
1000 1 10 1000 10000 106 1.07 × 10301

Table 6: Growth of common complexity classes for increasing n. The contrast highlights
why logarithmic and linear algorithms scale better than quadratic or exponential ones.

100 log2 n
Relative growth (scaled)

n
80 n log2 n (scaled)
n2 (scaled)
60 2 n (compressed)

40

20

0
10 20 30 40 50 60 70 80 90 100
n

Figure 5: Contrasting asymptotic growth rates. Some curves are scaled to fit within the
same axes. Note how quickly quadratic and exponential functions dominate compared to
logarithmic and linear growth.

In summary, Big-O and its complementary notations provide a rigorous yet practical
framework for evaluating algorithm efficiency. By ignoring irrelevant constants and focusing
on dominant terms, they allow us to predict scalability, compare algorithms fairly, and
understand why certain approaches remain viable for massive inputs while others collapse
under growth. Together, Table 6 and Figure 5 illustrate the central lesson: asymptotic
analysis is not merely mathematical abstraction but an essential guide for algorithm design
and selection.

8.2 Properties of Big-O

Big-O notation is one of the most powerful tools in algorithm analysis, but it must always
be applied with caution. Its purpose is to describe the growth rate of functions rather than
their precise runtime. Two algorithms can both belong to O(n), yet one may run in 2n
steps while another requires 2000n steps. Asymptotic classes therefore provide valuable

Khobzaoui Abdelkader 25 2025–2026

UDL — FSE/Informatique Algorithm analysis

guidance about scalability but do not resolve close comparisons where constant factors
or small input sizes dominate; in those cases, empirical profiling or more detailed cost
models are indispensable. Moreover, Big-O represents an asymptotic upper bound and
is usually interpreted as a worst-case measure. Importantly, belonging to the same O
class does not imply equality: if f (n) = O(g(n)) and h(n) = O(g(n)), it does not follow
that f (n) = h(n). For instance, n2 + 2n = O(n2 ) and n3 + 20n + 50 = O(n3 ), but clearly
the two functions are not identical. The notation signals comparable growth trends, not
functional equivalence. The key algebraic properties of Big-O, which make it useful in
combining and simplifying complexity expressions, can be summarized as follows:

1. Sum rule. If f (n) = O(g(n)) and h(n) = O(g(n)), then

f (n) + h(n) = O(g(n)).

More generally, the largest term dominates a sum. For instance, O(n) + O(log n) =
O(n).

2. Product rule. If f (n) = O(g(n)) and h(n) = O(k(n)), then

f (n) · h(n) = O(g(n)k(n)).

For example, O(n) · O(log n) = O(n log n). This explains why nested loops multiply
iteration counts.

3. Monotonicity. If g(n) ≤ h(n) for large n and f (n) = O(g(n)), then f (n) = O(h(n)).
Enlarging the bounding function cannot invalidate the relation.

4. Reflexivity. Any function is trivially an upper bound for itself:

f (n) = O(f (n)).

Another important guideline concerns constants and tightness. Any fixed constant C is
O(1), since it does not grow with n. However, constants must not be confused with growth
rates: ignoring them is safe, but misusing the rules can lead to incorrect conclusions. For
example,
n
n(n + 1)(2n + 1)
i2 = = Θ(n3 ).
X

i=1 6
It would be wrong to argue that since each term i2 is O(n2 ), the entire sum must also be
O(n2 ). The accumulation over n terms increases the order of growth, and only by applying
proper summation identities do we obtain the correct cubic bound. A naive step such as

12 + 22 + · · · + n2 = O(max{12 , 22 , . . . , n2 }) = O(n2 )

Khobzaoui Abdelkader 26 2025–2026

UDL — FSE/Informatique Algorithm analysis

for i = 1 to n do
A[i] = 0 // O(1) per iteration
end for

for j = 1 to n do
for k = 1 to n do
B[j][k] = j+k // O(1) per inner iteration
end for
end for

Figure 6: contrast between sequential and nested loops

is misleading, because the true asymptotic is O(n3 ). This example illustrates why Big-O,
while abstracting details, still requires precise reasoning.
A short pseudocode fragment illustrates how the rules apply in practice:
The first loop executes n assignments, giving O(n). The nested double loop performs
n×n = n2 operations, contributing O(n2 ). By the sum rule, the total cost is O(n)+O(n2 ) =
O(n2 ). Within the nested structure, the product rule justifies multiplying the iteration
counts of the inner and outer loops. This systematic reasoning allows us to translate
raw iteration counts into meaningful asymptotic classes. Figure 6 illustrates the contrast
between sequential and nested loops: in the former, costs add and the largest term
dominates; in the latter, iteration counts multiply.
In summary, Big-O remains indispensable because it abstracts away machine-specific
details and focuses on scalability. But like any abstraction, it must be applied responsibly:
constants may be ignored but not confused with growth, summations must be evaluated
properly, and algebraic rules must be respected. With these guidelines in mind—and
supported by worked examples and visual intuition such as Figure 6—Big-O provides a
reliable framework for analyzing and comparing algorithms.

8.3 Basic Mathematical Formulas

In the study of algorithm complexity, sums of sequential terms frequently arise. Con-
sequently, mastering the fundamental mathematical formulas for such sums is crucial.
Among the most commonly encountered are arithmetic series, geometric series, sums
of squares, sums of logarithms, and recurrence relations. These closed-form expressions
enable direct and simplified assessment of algorithmic complexity and are used extensively
in analyzing loop structures, recursive functions, and asymptotic growth.

Arithmetic Sequence An arithmetic sequence is one in which two consecutive terms differ
by a constant value. For example, 1, 3, 5, 7, . . . is an arithmetic sequence with common

Khobzaoui Abdelkader 27 2025–2026

UDL — FSE/Informatique Algorithm analysis

difference d = 2. In general, such a sequence is written as:

a1 , (a1 + d), (a1 + 2d), . . . , (a1 + (n − 1)d),

where a1 is the first term, d the common difference, and n the number of terms.
The sum of the first n terms is given by:

n(a1 + an )
Sn = , an = a1 + (n − 1)d.
2

Sum of Squares The sum of squares of the first n natural numbers is another frequently
used formula, especially when analyzing nested loops or quadratic-time algorithms:
n
n(n + 1)(2n + 1)
k2 =
X
.
k=1 6

Asymptotically, this sum grows as Θ(n3 ). Example in algorithms: an algorithm with an

outer loop running n times and an inner loop running i times (for i = 1 to n) executes
i=1 i operations, yielding cubic growth in the worst case.
Pn 2

Geometric Sequence A geometric sequence is one in which consecutive terms differ by

a fixed ratio r, called the common ratio. For example, 1, 3, 9, 27, 81, . . . is a geometric
sequence with r = 3.
If a is the first term, then the n-th term is arn−1 , and the sum of the first n terms is:

a(rn − 1)
Sn = a + ar + ar2 + · · · + arn−1 = , (r ̸= 1).
r−1

Example: for a = 1 and r = 2, we obtain the sequence 1, 2, 4, . . . , 2n−1 with sum

Sn = 2n − 1. This value corresponds to the maximum unsigned integer representable in n
binary digits.

Sum of Logarithms of an Arithmetic Sequence Another commonly needed result in

complexity analysis is the sum of logarithms of an arithmetic sequence:

log(a1 ) + log(a1 + d) + log(a1 + 2d) + · · · + log(a1 + (n − 1)d).

For a1 = 1 and d = 1, this becomes:

log(1) + log(2) + · · · + log(n) = log(n!).

Khobzaoui Abdelkader 28 2025–2026

UDL — FSE/Informatique Algorithm analysis

By Stirling’s approximation,
√  n
n
n! ≈ 2πn ,
e

so,
log(n!) ≈ 21 log(2π) + 21 log(n) + n log(n) − n.

Thus, for asymptotic analysis:

log(1) + log(2) + · · · + log(n) ≈ n log(n).

Floor and Ceiling Functions In algorithm design, indices or bounds often require integer
rounding. Two important functions help here:

• The floor function, ⌊x⌋, is the largest integer less than or equal to x.

• The ceiling function, ⌈x⌉, is the smallest integer greater than or equal to x.

For example, in binary search, the middle index low+high

2
must be rounded down or up to
ensure it remains an integer.

Recurrence Relations Many recursive algorithms are analyzed using recurrence relations,
which define each value in terms of earlier ones. For example, factorial can be defined as:

1

n = 0 or 1,
n! =
n · (n − 1)!

otherwise.

Similarly, the running time of recursive algorithms often satisfies a recurrence such as:

b

n = 1 (base case),
T (n) =
aT (f (n)) + g(n)

otherwise.

For factorial, the recurrence for runtime is:


b

n = 1,
T (n) =
T (n − 1) + c

otherwise,

which solves to T (n) = b + nc by repeated substitution. Other techniques for solving

recurrences include the Master Theorem, change of variables, and induction.
Summary. These formulas — arithmetic and geometric series, sums of squares and
logarithms, floor/ceiling functions, and recurrence relations — form the mathematical
backbone of complexity analysis. They appear repeatedly in analyzing loops, recursive

Khobzaoui Abdelkader 29 2025–2026

UDL — FSE/Informatique Algorithm analysis

algorithms, and divide-and-conquer methods, enabling precise derivations of asymptotic

behavior.

8.4 Recurrence Relation Solving Methods

Recursive algorithms often give rise to recurrence relations, mathematical expressions that
describe the running time of a function in terms of smaller instances of itself. Solving
these recurrences is essential for determining asymptotic complexity. Over time, computer
scientists have developed several powerful methods for handling recurrences, each with its
own strengths and limitations. The most commonly used techniques include:

• Repeated Substitution (Iterative Expansion): Expands the recurrence step by step

until a pattern emerges, then sums the resulting series. This method is simple,
intuitive, and well-suited to basic recurrences.

• Recursion Tree Method: Represents recursive calls as a tree of subproblems, sum-

ming the work across levels. It provides strong intuition and often reveals whether
recursion or combination dominates the overall cost.

• Master Theorem: A direct tool for divide-and-conquer recurrences of the form

T (n) = aT (n/b) + f (n), where it compares f (n) with nlogb a to give asymptotic
solutions.

• Change of Variables: Reparameterizes the problem (e.g., n = 2k ) to simplify analysis,

particularly when logarithmic terms or powers of two are involved.

• Guess-and-Prove (Induction): Involves hypothesizing a solution form (often guided

by recursion trees) and rigorously proving correctness by induction.

• Linear Homogeneous Equations: Uses characteristic polynomials to solve recurrences

with constant coefficients, a staple technique in discrete mathematics.

In algorithm analysis, the two most important approaches are Repeated Substitution for
building intuition and the Master Theorem for handling divide-and-conquer algorithms.
We illustrate both below.

Repeated Substitution Method

The repeated substitution (or iterative expansion) method replaces a recurrence with
smaller and smaller instances until reaching the base case. This reveals a pattern that can
then be expressed in closed form.

Khobzaoui Abdelkader 30 2025–2026

UDL — FSE/Informatique Algorithm analysis

Example 1: Factorial Recurrence. The recursive factorial function leads to:


b n = 1,


T (n) =
T (n − 1) + c otherwise,



where b and c are constants. Expanding step by step:

T (n) = T (n − 1) + c = T (n − 2) + 2c = · · · = T (1) + (n − 1)c = b + (n − 1)c.

Hence T (n) = Θ(n).

Example 2: Divide-and-Conquer Recurrence. Merge Sort gives:


1 n = 1,


T (n) =
2T (n/2) + n n > 1.



Substituting repeatedly:

T (n) = 2T (n/2) + n = 4T (n/4) + 2n = 8T (n/8) + 3n = · · · = 2i T (n/2i ) + in.

When n/2i = 1, i.e., i = log2 n, we obtain:

T (n) = nT (1) + n log n = Θ(n log n).

This analysis can also be visualized using a recursion tree, shown in Figure 7. Each
level contributes cost n, and with log2 n levels, the total is n log n.

level 0: n
n

level 1: n
n n
2 2

level 2: n
n n n n
4 4 4 4 depth = log2 n
total = n log n

Figure 7: Recursion tree for T (n) = 2T (n/2) + n. Each level costs n, and there are log2 n
levels, giving T (n) = Θ(n log n).

Khobzaoui Abdelkader 31 2025–2026

UDL — FSE/Informatique Algorithm analysis

The Master Theorem

The Master Theorem is a cornerstone tool for analyzing divide-and-conquer recurrences:

n
 
T (n) = aT + f (n),
b

where a ≥ 1 is the branching factor, b > 1 the reduction factor, and f (n) the cost of
dividing and combining. Let nc = nlogb a . Three cases arise:
1. Recursion Dominates: If f (n) = O(n1−ε
c ), then T (n) = Θ(nc ).

2. Balanced Case: If f (n) = Θ(nc logk n), then T (n) = Θ(nc logk+1 n).

3. Work Dominates: If f (n) = Ω(n1+ε

c ) and the regularity condition holds, then
T (n) = Θ(f (n)).
Examples:
• Merge Sort: T (n) = 2T (n/2) + Θ(n) ⇒ Θ(n log n).

• Strassen’s Matrix Multiplication: T (n) = 7T (n/2) + Θ(n2 ) ⇒ Θ(nlog2 7 ).

• Binary Search: T (n) = T (n/2) + Θ(1) ⇒ Θ(log n).

Comparison of Methods

For reference, Table 7 summarizes the key solving methods, their applicability, and
canonical examples.

Method Applicability / Strengths Example

Repeated Substi- Simple, intuitive; expands until T (n) = T (n − 1) + c ⇒
tution base case, useful for linear recur- Θ(n)
rences
Recursion Tree Visualizes work across levels, good T (n) = 2T (n/2) + n ⇒
for intuition and bounds Θ(n log n)
Master Theorem Direct asymptotic classification of Merge Sort, Strassen, Bi-
aT (n/b) + f (n) recurrences nary Search
Change of Vari- Simplifies when n = 2k or loga- T (n) = 2T (n/2) + n ⇒
ables rithms appear Θ(n log n)
Guess-and-Prove Flexible; works with intuition and T (n) = 2T (n/2) + n2 ⇒
induction Θ(n2 )
Linear Homoge- Solves constant-coefficient recur- T (n) = 2T (n − 1) +
neous Equations rences systematically 3T (n − 2)

Table 7: Comparison of recurrence relation solving methods.

Khobzaoui Abdelkader 32 2025–2026

UDL — FSE/Informatique Algorithm analysis

Summary. Recurrence relations capture the cost of recursive algorithms, and mastering
their solutions is central to algorithm analysis. Substitution and recursion trees provide
intuition and exact solutions for basic recurrences, while the Master Theorem generalizes
to a broad class of divide-and-conquer algorithms. Together with change of variables,
induction, and linear methods, these tools equip us to analyze the complexity of nearly
any recursive process.

9 Determining the Big-O for Different Algorithm Structures

A structured algorithm is typically composed of a combination of different statement types,
each contributing differently to the overall time complexity. By systematically analyzing
these structures, we can determine the asymptotic cost of most algorithms without running
code or measuring runtimes. This approach provides a cookbook of rules for reasoning
about scalability in a machine- and language-independent way. The major categories are:

1. Simple statements

2. Sequences of statements

3. Conditional (selection) statements

4. Loops

5. Non-recursive subprogram calls

6. Recursive subprogram calls

9.1 Simple Statements

A simple statement is one that does not involve any control flow (e.g., no loops or recursion).
Examples include assignments, arithmetic operations, and comparisons.
Such statements execute in constant time:

T (n) = O(1).

9.2 Sequence of Statements

When multiple statements are executed sequentially, the total complexity is the sum of
their individual complexities. Asymptotically, only the largest growth term matters.
Example:
T (n) = O(1) + O(n) + O(n2 ) + O(log n) = O(n2 ).

Khobzaoui Abdelkader 33 2025–2026

UDL — FSE/Informatique Algorithm analysis

9.3 Conditional (Selection) Statements

Conditional statements (if–else, switch) execute only one branch at a time.
To analyze their complexity:
• Evaluate the cost of the condition.

• Take the maximum of the branch costs (since only one path runs).
Example:
if (condition) {
O(n)
} else {
O(n^2)
}

The result is:

T (n) = max(O(n), O(n2 )) = O(n2 ).

9.4 Loop Statements

Loops often dominate the cost of algorithms. Their complexity depends on both the body
and the number of iterations.

• Let f (n) = cost of the loop body.

• Let g(n) = number of iterations.

• Then T (n) = O(f (n) · g(n)).

Example 1: Simple loop

for (i = 1; i <= n; i++) {
// O(1) operation
}

Here f (n) = O(1), g(n) = O(n), so T (n) = O(n).

Example 2: Nested loops
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
// O(1) operation
}
}

Khobzaoui Abdelkader 34 2025–2026

UDL — FSE/Informatique Algorithm analysis

Here T (n) = O(n2 ).

Example 3: Triangular loops

for (i = 1; i <= n; i++) {

for (j = 1; j <= i; j++) {
// O(1) operation
}
}

Here: n
n(n + 1)
T (n) = i= = Θ(n2 ).
X

i=1 2

9.5 Non-Recursive Subprogram Calls

For non-recursive calls:

• Determine the complexity of the subprogram, say O(g(n)).

• If it is invoked f (n) times, the total cost is:

T (n) = O(f (n) · g(n)).

Example: If a function costs O(n) and is called O(log n) times, then

T (n) = O(n log n).

9.6 Recursive Subprogram Calls

Recursion leads to recurrence relations:

1. Express T (n) in terms of smaller subproblems.

2. Solve the recurrence via repeated substitution, recursion trees, or the Master Theo-
rem.

Example 1: Fibonacci

F(n) {
if (n <= 1) return n;
return F(n-1) + F(n-2);
}

Khobzaoui Abdelkader 35 2025–2026

UDL — FSE/Informatique Algorithm analysis

This gives
T (n) = T (n − 1) + T (n − 2) + O(1) = O(2n ).

Example 2: Merge Sort

 
T (n) = 2T n
2
+ O(n).

By the Master Theorem:

T (n) = O(n log n).

These structural rules, combined with the summary table (Table 8), provide both intuition
and a quick reference for analyzing algorithms. They allow us to translate raw code into
asymptotic behavior, highlighting scalability without being distracted by constant factors
or machine-specific details.

Structure Example (pseudocode) Complexity

Simple statement x = 5; y = x + 1; O(1)
Sequence O(1) + O(n) + O(n^2) O(n2 )
Conditional if cond then O(n) else O(n^2) max(O(n), O(n2 )) = O(n2 )
Simple loop for i=1..n do O(1) O(n)
Nested loops for i=1..n; for j=1..n do O(1) O(n2 )
Triangular loop for i=1..n; for j=1..i do O(1) Θ(n2 )
Non-recursive calls f (n) calls to O(g(n)) function O(f (n) · g(n))
Recursive calls T (n) = aT (n/b) + f (n) Depends (solve recurrence)

Table 8: Cheatsheet of common program structures and their Big-O complexities.

10 Summary
Algorithm analysis is fundamental to computer science, providing the theoretical framework
to evaluate and compare algorithmic solutions. Through complexity analysis, we can:

• Predict performance independently of hardware and implementation details.

• Select algorithms based on scalability requirements.

• Identify bottlenecks and opportunities for optimization.

• Understand theoretical trade-offs in computational problems.

The key tools covered in this chapter include:

Khobzaoui Abdelkader 36 2025–2026

UDL — FSE/Informatique Algorithm analysis

Big O Notation: Provides asymptotic upper bounds on runtime growth with respect to
input size.

Complexity Rules: Systematic methods to analyze sequences, conditionals, loops, and

subprogram calls.

Recurrence Relations: Mathematical models of recursive algorithms, solved by substitu-

tion, recursion trees, or the Master Theorem.

Master Theorem: A direct tool for analyzing divide-and-conquer recurrences without

lengthy derivations.

These methods form the foundation for designing efficient algorithms that scale grace-
fully with problem size. Whether creating new solutions or choosing among existing ones,
complexity analysis provides the rigorous framework for informed engineering decisions.

11 Exercises
1. Step counting (loops). Consider the pseudocode:

s <- 0
for i <- 1 to n do
for j <- 1 to i do
s <- s + 1

(a) Count exactly the number of assignments to s.

2. Asymptotic classification. For each function, give the tightest Big-O class and justify:
√
(i) 7n2 + 3n log n + 100 (ii) n log n + n/ log n (iii) 2n + n3 (iv) n log3 n (v) nlog2 7

3. Logarithm rules and equivalences. Prove or disprove each statement: (a) log(nk ) ∈
Θ(log n) for any fixed k > 0. (b) loga n ∈ Θ(logb n) for any a, b > 1. (c) log n! ∈
Θ(n log n).

4. Dominance via limits. Let f (n) = n log n and g(n) = n1.1 . Use limits to decide
whether f ∈ o(g), f ∈ ω(g), or f ∈ Θ(g). Explain the general method.

5. Recurrence I (substitution). Solve and justify using substitution: (a) T (n) =

T (n−1)+2, T (1) = 1. (b) T (n) = 2T (n/2)+n, T (1) = 1. (c) T (n) = T (n/2)+log n,
T (1) = 1.

Khobzaoui Abdelkader 37 2025–2026

UDL — FSE/Informatique Algorithm analysis

6. Recurrence II (Master Theorem). Give tight bounds (and identify the Master
case if applicable): (a) T (n) = 3T (n/3) + n log n (b) T (n) = 4T (n/2) + n (c)
T (n) = 8T (n/2) + n2 (d) T (n) = 2T (n/2) + n/ log n

7. Recursion tree method. Use a recursion tree to derive T (n) for T (n) = T (n/2) +
T (n/4) + n (assume n is a power of 4). Summarize level costs and total.

8. Worst/average/best cases. For linear search on an array of size n containing the

target exactly once with uniform random position: (a) Derive best, worst, and
expected number of comparisons.

9. Binary search analysis. (a) Prove that binary search does at most ⌊log2 n⌋ + 1
comparisons in the worst case. (b) Show that the recursion depth is O(log n) for the
recursive version.

10. Transitivity and counterexamples. (a) Prove: if f ∈ O(g) and g ∈ O(h) then
f ∈ O(h). (b) Give a counterexample to: if f ∈ O(g) then g ∈ Ω(f ) with the same
hidden constant.

11. Little-o vs Big-O. For each claim, decide true/false and justify: (a) If f ∈ o(g)
then f ∈ O(g). (b) If f ∈ O(g) then f ∈ o(g). (c) If f ∈ Θ(g) then f ∈ O(g) and
f ∈ Ω(g).

12. Amortized analysis (dynamic array). Consider a dynamic array that doubles its
capacity when full; append(x) inserts at the end. (a) Show that the amortized cost
of append is O(1) over any sequence of m appends. (b) Explain one-shot expensive
operations and why amortized ̸= worst-case per operation.

13. Empirical vs theoretical growth. Design an experiment to compare selection sort

(O(n2 )) and merge sort (O(n log n)) on n ∈ {103 , 104 , 105 }: (a) Describe measurement
protocol (trials, warm-up, timing). (b) Predict cross-over behavior and explain
variance sources (cache, constants).

14. Break-even analysis. An algorithm A runs in 100n log2 n operations; algorithm B

runs in n2 /4 operations. (a) Find the smallest n (integer) for which A beats B. (b)
Discuss sensitivity to constant factors and base of logarithms.

Khobzaoui Abdelkader 38 2025–2026