Chapter 2

10/2/2023
Mathematics
Standard notion and common
functions
1
 Mathematical background for
Analysis of Algorithms
• The analysis of algorithms requires the need to draw
upon a body of mathematical operations. Some of
these operations are as simple as high school algebra

10/2/2023
while others are abit complex
• Along with learning how to manipulate asymptotic
notations and solving recurrences, there is the need
to learn other concepts and methods in order to
analyze algorithms
• Examples of these concepts and methods include:-

2
• Methods for evaluating bounding
summations
• Sets, relations, functions, graphs and
trees

10/2/2023
• Counting: permutations and
combination
• Probability and statistics

3
Summations
• When an algorithms contains an iterative control
construct for instance while and for loop its
running time can be expressed as the sum of the
times spent on each execution of the body of the

10/2/2023
loop.
• Summation and product formulas
• Given a sequence of numbers a1, a2,...,an, the
finite sum of those numbers can be written as
•
n

a
k =1
k
4

• (if n = 0, the summation is defined to be 0).

Summations formulas and properties
• Arithmetic Series

( )
n
1

k =1
k = 1 + 2 + ... + n =
2
n ( n + 1) =  n 2

• Geometric or exponential Series

n+1
n
−1 x

k =1
x = 1 + x + x + ... + x =
k 2

x −1
n

• For real x ≠1
5

10/2/2023
Summations formulas and properties
• Sums of Squares and Cubes
n
n(n + 1)(2n + 1)

k =1
k =
2

6
2
n
n (n + 1)
2


k =1
k =3

4
6

10/2/2023
Bounding summations
Methods
• Most of the summations cannot be computed
precisely when determining the run time of

10/2/2023
algorithms with iterative controls. In such cases
there is need to find asymptotic upper and lower
bound for the summation.
• In the ideal case, a Θ() bound is used.
• There are many techniques for bounding
summations

7
➢Mathematical Induction
• This is the most basic way to evaluate a series
• For example: prove the bound for the following equation
𝑛(2𝑛+1)(𝑛+1)
• σ𝑛𝑘=1 𝑘 2 =
6

10/2/2023
➢Bounding the terms
• This is a method of bounding summations done by using the
largest (smallest) value of terms to bound others
• a1 + a2 + . . . an ≤ amax + amax + . . . + amax = n · amax
• a1 + a2 + . . . an ≥ amin + amin + . . . + amin = n · amin

• Example
➢Splitting summations 8
• Better bounds can be obtained by partitioning the range of
index and then bounding each of the results series
Summation conclusion
• Given a sum to calculate the bound for it. You do the
following

10/2/2023
➢Express it in terms of basic summations for which you
know the bound
➢Guess the bound and prove it by induction
➢Obtain upper and lower bounds by bounding terms
and/or splitting

9
 Sets
• A set is a collection of distinguishable objects;
called members or elements
• A set cannot contain the same element more than
once; a variation of this is called multiset
• Given a set say S and element x then we can
write:
•
xS
• (read as “x is in S”)
•
• OR
• xS
• (read as “x is not in S”) 10

10/2/2023
Frequently used set

• θ

10/2/2023
the empty set
•Z
set of integers {…, -2,-1,0,1,2,…}
•R
set of real numbers
•N
set of natural numbers {0,1,2,…}
11
• Recurrence Relations
• Algorithms can be analyzed through a direct mapping
from a recursive representation of a program to a
recursive representation of a function describing its
properties.

10/2/2023
• Recurrence is used to efficiently calculate the
quantity in a question, it is done by first computing
the small values in order to get a feeling of how the
values are growing.

12
Probability and statistics
• Probability is an essential tool for design and
analysis of probabilistic and randomized

10/2/2023
algorithms.
• Probability is defined in terms of a sample space
say S
• For instance when determining the expected
runtime of a comparison based sort algorithm,
the following steps would be followed to solve
the problem
13
• Define the distribution over all possible inputs to the
algorithm
• For example N! permutations of ordering N distinct
1
numbers are equally likely
𝑁!

10/2/2023
• Determine the run time for each possible input
• Compute the expected runtime by summing up over
all possible inputs the probability of the input times
the runtime for the input
• 𝐸 𝑅𝑢𝑛𝑡𝑖𝑚𝑒 = 𝑠𝑢𝑚𝑖 = 1 … , 𝑁! ሼ𝑃 𝑖 ∗
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑖 ሽ = 𝑠𝑢𝑚𝑖 = 1, . . , 𝑁! ሼ𝑅𝑢𝑛𝑡𝑖𝑚𝑒(𝑖)ሽ/𝑁!

14
• If the above steps are followed while analysing
quicksort algorithm ignoring the pivot the
expected runtime of quicksort is 𝑶(𝑵 𝒍𝒐𝒈 𝑵)
while the worst-case runtime is 𝑶(𝑵𝟐 )

10/2/2023
15
 Monotonicity:
• Monotonically increasing function f(n);

If m≤n implies that f(m)≤f(n)

10/2/2023
• Monotonically decreasing function f(n);

If m ≥ n implies that f(m)≥f(n)

• Strictly increasing function f(n);

If m<n implies that f(m)<f(n)

• Strictly decreasing function f(n);

If m>n implies that f(m)>f(n) 16

Floors and Ceilings
• The floor and ceiling function give the
nearest integer up and down
• Example: what is the floor and ceiling of 5.6
• The floor of 5.6 is 5
• The ceiling off 5.6 is 6
• For integer the floor and ceiling does not
change
• For example : the floor and ceiling of 3 is 3
• Symbols
• The symbols for the floor and ceiling are like
the square brackets with the top or bottom 17
part missing
10/2/2023
• Floor function-⌊x⌋
• Ceiling function- ⌈x⌉
• The word form for the symbol is
• Floor(x)
• Ceil(x)

10/2/2023
• Definition
• The floor of x (⌊x⌋) is the greatest integer less than or equal to x
x=2.6; ⌊x⌋=2
x= -1.3; ⌊x⌋=-2

18
• The Ceiling of x(⌈x⌉) is the least integer greater or equal to x
x=2.6; ⌈x⌉=3
x= -1.3; ⌈x⌉=-1

10/2/2023
19
 Polynomials
• Given a nonnegative integer d, a polynomial in n of degree d is the
a function p(n) of the form:

d
p(n) =  ain i

i =0
• Where a0, a1, …, ad are coefficients of the polynomial and ad≠ 0

20

10/2/2023
 Exponentials
• For all real a>0, m and n, the following hold:
• a0 =1
• a1 =a
• a-1 =1/a
• (am)n = amn
• (am)n= (an)m

2 3  i
x x x
e x = 1 + x + + + ... = 
2! 3! i =0 i! 21

10/2/2023
*
 Logarithms
• The following notations are adopted
• Lgn = log2n (binary logarithm)
• Lnn = logen (natural logarithm)
k
• k
Lg n = (logn) (Exponentiation)
• Lg Lgn = lg(lgn) (composition)

22

10/2/2023
*
 Factorials and Functional
Iteration
1 if n =0

n! = 
•

−
•
•
 n * ( n 1)! if n >0

• Functional Iteration
(i)
• f (n) – function f(n) iteratively applied i
times to an initial value of n
23

10/2/2023
*
 Fibonacci Numbers
• Defined as follows:
• F0 =0
• F1 =1
• Fi = Fi-1 +Fi-2 for i >=2
• Each Fibonacci number is the sum of the two
previous ones:
• 0,1,1,2,3,5,8,13,21,34,55,…

24

10/2/2023
*